#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define int long long
int c,t,n,k;
map<string,bool> ma;
struct EDGE {
	int v,id;
};
vector<EDGE> g[N],cyq;
vector<int> g1[N];
void dfs(int x,int fa,int id) {
	vector<int> man;
	if(id) man.push_back(id);
	for(auto v:g[x]) {
		man.push_back(v.id);
		dfs(v.v,x,v.id);
	}
	for(int i=0;i<man.size();i++) {
		for(int j=i+1;j<man.size();j++) {
			g1[man[i]].push_back(man[j]);
			g1[man[j]].push_back(man[i]);
		}
	}
}
bool vis[N];
void dfs1(int x,int fa) {
	vis[x]=1;
	for(auto v:g1[x]) {
		if(v==fa) continue;
	}
}
signed main() {
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	cin>>c>>t;
	while(t--) {
		cin>>n>>k;
		for(int i=1;i<n;i++) {
			int u,v;
			cin>>u>>v;
			g[u].push_back(EDGE{v,i});
			g[v].push_back(EDGE{u,i});
		}
//		dfs(1,0);
//		for(int i=1;i<=k;i++) {
//			int u; cin>>u;
//			dfs1(u,0);
//		}
		cout<<3<<endl;
	}
	return 0;
}
