#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
vector<int> map[100001];
int vis[100010];
int n,m,s;
bool flag=false;
void bfs()
{
    queue<int> q;
    q.push(s);
    vis[s]=0;
    int p;
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(int i=0;i<map[p].size();i++)
        {
            if(vis[map[p][i]]==-1)
            {
                if(vis[p]==1)
                    vis[map[p][i]]=0;
                else
                    vis[map[p][i]]=1;
                q.push(map[p][i]);
            }
            else
            {
                  if(vis[map[p][i]]==vis[p])
                        flag=true;
            }
        }
}
int main()
{
    int T,cas;
    scanf("%d",&T);
    for(cas=1;cas<=T;cas++)
    {
        scanf("%d%d%d",&n,&m,&s);
        memset(vis,-1,sizeof(vis));
        flag=false;
        for(int i=0;i<n;i++)
            map[i].clear();
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        bfs();
        printf("Case %d:",cas);
        if(flag)
            printf(" YES\n");
        else
            printf(" NO\n");
    }
    return 0;
}