#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define MAXN 1111

 #define FILL(a,b) memset(a,b,sizeof(a))

 int n,m,ly[MAXN];

 bool mark[MAXN];

 vector<int>g[MAXN];

 int dfs(int u)

 {

     for(int i=;i<g[u].size();i++){

         int v=g[u][i];

         if(!mark[v]){

             mark[v]=true;

             if(ly[v]==-||dfs(ly[v])){

                 ly[v]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int MaxMatch()

 {

     int res=;

     FILL(ly,-);

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

         FILL(mark,false);

         res+=dfs(i);

     }

     return res/;

 }

 int main()

 {

     int _case,u,v,t=;

     scanf("%d",&_case);

     while(_case--){

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

         for(int i=;i<=n;i++)g[i].clear();

         while(m--){

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

             g[u].push_back(v);

             g[v].push_back(u);

         }

         printf("Case %d: %d\n",t++,n-MaxMatch());

     }

     return ;

 }