#include<bits/stdc++.h>
using namespace std;
int c,t,n,k;
struct edge{
	int id,v;
};
vector<edge> g[1000001];
edge a[1000001];
int main(){
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	cin>>c>>t;
	while(t--){
		for(int i=1;i<=n;i++)g[i].clear();
		cin>>n>>k;
		for(int i=1,x,y;i<n;i++)cin>>x>>y,g[x].push_back((edge){i,y}),g[y].push_back((edge){i,x});
		cout<<3<<"\n";
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

