/*
    题意：给出一个无向图，一个起点，问是否在某个时候，这个人有可能在所有点都可以出现
           人不能停留在原地
    画一下图就知道，只要存在奇圈，那么奇圈的点就可以任何时刻都出现人
    同时，对于奇圈外的，奇圈可以源源不断地传到奇圈外
    这样肯定存在某个时刻，其他点也可以同时出现人（因为源源不断传出来，所以肯定会波及所有）
*/
#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;
}