xay loves trees

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=5e6+10;
int n,m,r;
int e,h[maxn],ne[maxn],ver[maxn];
int tot,h1[maxn],ne1[maxn],ver1[maxn];
int a[maxn*4],laz[maxn*4];
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn]; 
int res=0,ans=0;
int dist[maxn];
void add1(int x,int y){
    ver1[++tot]=y;
    ne1[tot]=h1[x];
    h1[x]=tot;
}
void add(int x,int y){
    ver[++e]=y;
    ne[e]=h[x];
    h[x]=e;
}
void pushdown(int rt){
    laz[rt*2]=laz[rt];
    laz[rt*2+1]=laz[rt];
    a[rt*2]=laz[rt];
    a[rt*2+1]=laz[rt];
    laz[rt]=0;
}
void build(int rt,int l,int r){

    if(l==r){
        a[rt]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
int query(int rt,int l,int r,int L,int R){
  //  cout<<l<<"uu"<<r<<" "<<L<<" "<<R<<" "<<rt<<endl;
    int ans=0;
    if(L<=l&&r<=R){
        return a[rt];
    }
    if(laz[rt])pushdown(rt);
    int mid=(l+r)>>1;
    if(L<=mid)ans=max(ans,query(rt*2,l,mid,L,R));
    if(R>mid)ans=max(ans,query(rt*2+1,mid+1,r,L,R));
    return ans;
}
void update(int rt,int l,int r,int pos,int k){
    //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<k<<endl;
   // cout<<l<<"SS"<<r<<endl;
    if(l==r){
        laz[rt]=k;
        a[rt]=k;
        return;
    }
    int mid=(l+r)>>1;
   // if(laz[rt])pushdown(rt);
    if(pos<=mid)update(rt*2,l,mid,pos,k);
    if(pos>mid)update(rt*2+1,mid+1,r,pos,k);
    a[rt]=max(a[rt*2],a[rt*2+1]);
}
void dfs1(int x,int f,int deep){
    dep[x]=deep;siz[x]=1;fa[x]=f;
    int  maxson=-1;
    for(int i=h[x];i;i=ne[i]){
        int y=ver[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson){
            maxson=siz[y],son[x]=y;
        }
    }
}
void dfs2(int x,int topf){
    id[x]=++cnt;
    top[x]=topf;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=h[x];i;i=ne[i]){
        int y=ver[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
void updRange(int x,int k){
    //while(top[x]!=top[y]){
    //    if(dep[top[x]]<dep[top[y]])swap(x,y);
    //    update(1,1,n,id[top[x]],id[x],k);
    //    x=fa[top[x]];
    //}
    //if(dep[x]>dep[y])swap(x,y);
    update(1,1,n,id[x],k);
} 
int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=max(ans,query(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=max(ans,query(1,1,n,id[x],id[y]));
    return ans;
}
int qSon(int x){
    return query(1,1,n,id[x],id[x]+siz[x]-1);
}
//void updSon(int x,int k){
  //  update(1,1,n,id[x],id[x]+siz[x]-1,k);
//}
void dfs(int x,int fa,int u){
    int t=qRange(1,x);
    int t1=qSon(x);
   // cout<<qSon(4)<<" "<<x<<" "<<t<<"SS"<<t1<<endl;
    u=max(u,max(t1,t));
    ans=max(ans,dist[x]-u);
    updRange(x,dist[x]);
    for(int i=h1[x];i;i=ne1[i]){
        int y=ver1[i];
        if(y==fa)continue;
    //    cout<<"UU"<<y<<endl;
        dist[y]=dist[x]+1;
        dfs(y,x,u);
    }
    updRange(x,0);
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        ans=0;
        scanf("%d",&n);
        ans=0;
        e=tot=0;
        cnt=0;
        for(int i=0;i<=n+1;i++)dist[i]=h[i]=h1[i]=son[i]=id[i]=fa[i]=dep[i]=siz[i]=top[i]=0;
        r=1;
        for(int i=1;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add1(a,b);add1(b,a);
        }
        for(int i=1;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);add(b,a);
        }
        dfs1(r,0,1);
        dfs2(r,r);
        build(1,1,n);
        dist[1]=1;
        dfs(1,-1,0);
        printf("%d\n",ans);
    }
    return 0;
}