water problem

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10;
const int M=2e6+10;
int fa[N];
int siz[N];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
		fa[i]=i;
		siz[i]=1;
	}
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        if(find(u)==find(v)) continue;
        siz[find(v)]+=siz[find(u)];
        fa[find(u)]=find(v);
    }
    int ans=2;
    for(int i=1;i<=n;i++){
		if(find(i)==i&&(siz[i]&1)){
			ans=3;
		}
	}
    cout<<ans<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--){
		solve();
	}
    return 0;
}