#include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 1111

 #define MAXM 1111*1111

 struct Edge{

     int v,next;

 }edge[MAXM];

 int NE,head[MAXN];

 void addEdge(int u,int v){

     edge[NE].v=v; edge[NE].next=head[u]; head[u]=NE++;

 }

 int d[MAXN][];

 int dfs(int u,int k,int fa){

     if(d[u][k]!=-) return d[u][k];

     int res=k;

     for(int i=head[u]; i!=-; i=edge[i].next){

         int v=edge[i].v;

         if(v==fa) continue;

         if(k) res+=dfs(v,,u);

         else res+=max(dfs(v,,u),dfs(v,,u));

     }

     return d[u][k]=res;

 }

 int par[MAXN];

 int Find(int a){

     while(a!=par[a]){

         par[a]=par[par[a]];

         a=par[a];

     }

     return a;

 }

 void Union(int a,int b){

     int pa=Find(a),pb=Find(b);

     if(pa==pb) return;

     par[pb]=pa;

 }

 int main(){

     int t,n,m,a,b;

     scanf("%d",&t);

     for(int cse=; cse<=t; ++cse){

         NE=;

         memset(head,-,sizeof(head));

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

         for(int i=; i<=n; ++i) par[i]=i;

         while(m--){

             scanf("%d%d",&a,&b);

             addEdge(a,b); addEdge(b,a);

             Union(a,b);

         }

         memset(d,-,sizeof(d));

         int res=;

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

             if(par[i]==i) res+=max(dfs(i,,),dfs(i,,));

         }

         printf("Case %d: %d\n",cse,res);

     }

     return ;

 }