#include <bits/stdc++.h>

using namespace std;

#define pll pair < long long, long long>
#define all(a) a.begin(), a.end()
#define ull unsigned long long
#define pii pair < int, int >
#define np next_permutation
#define sz(a) (int)a.size()
#define sqr(x) ((x) * (x))
#define right stupid_right
#define left stupid_left
#define vi vector <int>
#define y1 stupid_cmath
#define ld long double
#define pb push_back
#define mp make_pair
#define ll long long
#define pi acosl(-1.0)
#define s second
#define f first
#define endl "\n"

const int inf = (int)1e9;
const double eps = 1e-9;
const int mod = 10000007;
const int N = 4 * (int)1e4 + 5;
const int sz = (int)5761509;

int n, m, timer, cur;
vector <int> g[100100];
set <int> gr[100100];
bool used[100100], was[100100];
int t[100100], f[100100], comp[100100];
set <pair <int, int> > ans;


void dfs(int v, int p = -1){
	used[v] = 1;
	t[v] = f[v] = timer++;
	for(int i = 0; i < g[v].size(); ++i){
		int to = g[v][i];
		if(to == p) continue;
		if(used[to]) f[v] = min(f[v], t[to]);
		else{
			dfs(to, v);
			f[v] = min(f[v], f[to]);
			if(f[to] > t[v]){
				ans.insert<(mp(min(to, v), max(to, v)));
			}
		}
	}
}

void dfs1(int v, int cl){
	comp[v] = cl;
	for(int i = 0; i < g[v].size(); ++i){
		int to = g[v][i];
		pii ex = mp(min(v, to), max(v, to));
		if(ans.find(ex) != ans.end()) continue;
		if(comp[to] == -1) dfs1(to, cl);
	}
}

void solve(){
	timer = 0;
	cur = 0;
	ans.clear();
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i){
		g[i].clear();
		t[i] = 0;
		f[i] = 0;
		comp[i] = -1;
		was[i] = 0;
		used[i] = false;
	}
	for(int i = 0, x, y; i < n; ++i){
		scanf("%d %d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(0);
	for(int i = 0, j = 0; i < n; ++i){
		if(comp[i] == -1){
			dfs1(i, j++);
		}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < g[i].size(); ++i){
			int to = g[i][j];
			gr[comp[i]].insert(comp[to]);
			gr[comp[to]].insert(comp[i]);
		}
	}
	for(int i = 0; i < n; ++i){
		if(gr[comp[i]].size() == 1 && !was[comp[i]]){
			cur++;
			was[comp[i]] = 1;
		}
	}
	printf("%d\n", (cur + 1) / 2);
}

int main() {
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; ++t){
        printf("Case %d: ", t);
        solve();
    }
}