#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int N=1e5+1; int n; //tree 1 int d[N]; vector<int>e1[N]; set<pair<int,int> >s[N]; //tree 2 vector<int>e2[N]; int ptr; int st[N],h[N]; int sp[2*N][20]; int lg[2*N]; int lca(int u,int v){ u=st[u],v=st[v]; if(u>v) swap(u,v); int k=lg[v-u+1]; return min(sp[u][k],sp[v-(1<<k)+1][k]); } void dfs1(int id,int p){ ++ptr;h[id]=h[p]+1; st[id]=ptr;sp[ptr][0]=h[id]; for(auto c:e2[id]){ if(c==p) continue; dfs1(c,id); ++ptr;sp[ptr][0]=h[id]; } } int ans=0; void add(int id,int v){ int u=st[v]; auto it=s[id].lower_bound({u,v}); if(it!=s[id].end()){ ans=max(ans,d[id]+lca(it->se,v)); } if(it!=s[id].begin()){ --it; ans=max(ans,d[id]+lca(it->se,v)); } s[id].insert({u,v}); } void dfs2(int id,int p){ int bc=id; d[id]=d[p]+1; for(auto c:e1[id]){ if(c==p) continue; dfs2(c,id); if(s[c].size()>s[bc].size()) bc=c; } s[id].swap(s[bc]); add(id,id); for(auto c:e1[id]){ if(c==p || c==bc) continue; for(auto d:s[c]) add(id,d.se); s[c].clear(); } } void solve(){ cin >> n;ptr=0;ans=0; for(int i=2; i<=2*n ;i++) lg[i]=lg[i/2]+1; for(int i=1; i<=n ;i++){ s[i].clear(); e1[i].clear();e2[i].clear(); } for(int i=1; i<n ;i++){ int u,v;cin >> u >> v; e1[u].push_back(v); e1[v].push_back(u); } for(int i=1; i<n ;i++){ int u,v;cin >> u >> v; e2[u].push_back(v); e2[v].push_back(u); } dfs1(1,0); for(int i=1; (1<<i)<2*n ;i++){ for(int j=1; j+(1<<i)-1<2*n ;j++){ sp[j][i]=min(sp[j][i-1],sp[j+(1<<(i-1))][i-1]); } } dfs2(1,0); cout << ans << '\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t;while(t--){solve();/*cout << endl;*/} }