/*
    題意：給出一個無向圖，一個起點，問是否在某個時候，這個人有可能在所有點都可以出現
           人不能停留在原地
    畫一下圖就知道，只要存在奇圈，那么奇圈的點就可以任何時刻都出現人
    同時，對于奇圈外的，奇圈可以源源不斷地傳到奇圈外
    這樣肯定存在某個時刻，其他點也可以同時出現人（因為源源不斷傳出來，所以肯定會波及所有）
*/
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int MAXN = 100005;

vector<int>G[MAXN];
bool flag;
int vi[MAXN];

void dfs(int u,int p,int dep)
{
    if(flag)return;
    vi[u]=dep;
    for(int i=0,size=G[u].size();i<size;i++)
    {
        int v=G[u][i];
        if(v==p)continue;
        if(vi[v]==dep){flag=true;return;}
        if(vi[v]==0)dfs(v,u,-dep);//注意是沒visit過的才繼續dfs
    }
}
int main()
{
    int T,t=1;
    scanf("%d",&T);
    while(T--)
    {
        printf("Case %d: ",t++);
        int n,m,s;
        scanf("%d%d%d",&n,&m,&s);
        for(int i=0;i<n;i++)
            G[i].clear();
        for(int i=0,a,b;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        memset(vi,0,sizeof(vi));
        flag = false;
        dfs(s,s,1);
        puts(flag?"YES":"NO");
    }
    return 0;
}