#include <bits/stdc++.h>

using namespace std;

int n,m,s,book[+];

vector<int> mp[+];

bool dfs(int u)

{

    queue <int>q;

    q.push(u);

    book[u]=;

    while(!q.empty())

    {

        int from = q.front();

        q.pop();

        for(int i=;i<mp[from].size();i++)

        {

            int tmp = mp[from][i];

            if(book[tmp]==-)

            {

                book[tmp]=!book[from];

                q.push(tmp);

            }

            else if(book[tmp]==book[from])

                return false;

        }

    }

    return true;

}

void init(){

    for(int i=;i<n;i++)

        mp[i].clear();

    memset(book,-,sizeof(book));

}

int main(){

    int ca=,t;

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d%d%d",&n,&m,&s);

        for(int i=;i<=m;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            mp[u].push_back(v);

            mp[v].push_back(u);

        }

        bool flag  = false ;

        for(int i=; i<n &&!flag ;i++)

        {

                if(book[i]==-&&!dfs(i))

                {

                    flag = true;

                    break;

                }

        }

        if(flag)printf("Case %d: YES\n",++ca);

        else printf("Case %d: NO\n",++ca);

    }

    return ;

}