#include<bits/stdc++.h> #include<bits/extc++.h> #pragma gcc optimize(2) #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcountll #define ldb long double using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned int uint; typedef __int128_t i128; typedef unsigned long long ull; typedef unsigned int uint; const int maxn=1e6+10,base=59,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n; vector<int>E1[maxn],E2[maxn]; struct _ {int mn,c;_(){}_(int _mn,int _c){mn=_mn,c=_c;}}; _ operator+(_ a,_ b){ if(a.mn<b.mn)return a; if(b.mn<a.mn)return b; return _(a.mn,a.c+b.c); } struct SegTree { struct __ { _ a;int lz; void push(int k){lz+=k,a.mn+=k;} }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){d[p].a=d[ls(p)].a+d[rs(p)].a;} void pd(int p){d[ls(p)].push(d[p].lz),d[rs(p)].push(d[p].lz);d[p].lz=0;} void modify(int l,int r,int s,int t,int p,int k){if(l>r)return; if(l<=s&&t<=r)return d[p].push(k);pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),k);if(r>mid)modify(l,r,mid+1,t,rs(p),k);pu(p); } }T; int fa[maxn],dfn[maxn],siz[maxn],cnt; ll res; void dfs(int u){ dfn[u]=++cnt,siz[u]=1; for(int x:E1[u])if(x!=fa[u])fa[x]=u,dfs(x),siz[u]+=siz[x]; } bool chk(int x,int y){return dfn[y]>=dfn[x]&&dfn[y]<dfn[x]+siz[x];} void add(int u){ for(int p:E2[u]){ if(chk(u,p))T.modify(1,dfn[p],1,n,1,-1),T.modify(dfn[p]+siz[p],n,1,n,1,-1); else T.modify(dfn[u],dfn[u]+siz[u]-1,1,n,1,-1); } } vector<int>Del[maxn]; void del(int u){ vector<int>vec; vector<int>son; for(int x:E1[u])if(x!=fa[u])Del[x].clear(),son.p_b(x),vec.p_b(dfn[x]+siz[x]-1); for(int x:E2[u]){ if(!chk(u,x))continue; int p=lower_bound(vec.begin(),vec.end(),dfn[x])-vec.begin(); Del[son[p]].p_b(x); } } void dfs2(int u){ add(u); res+=T.d[1].a.c; del(u); for(int x:E1[u])if(x!=fa[u]){ T.modify(dfn[x],dfn[x]+siz[x]-1,1,n,1,-1); T.modify(1,dfn[x]-1,1,n,1,1); T.modify(dfn[x]+siz[x],n,1,n,1,1); for(int p:Del[x])T.modify(dfn[p],dfn[p]+siz[p]-1,1,n,1,1); dfs2(x); for(int p:Del[x])T.modify(dfn[p],dfn[p]+siz[p]-1,1,n,1,-1); } } void slv(){ n=read();up(i,1,n)E1[i].clear(),E2[i].clear(); up(i,1,n-1){int x=read(),y=read();E1[x].p_b(y),E1[y].p_b(x);} up(i,1,n-1){int x=read(),y=read();E2[x].p_b(y),E2[y].p_b(x);} cnt=0,dfs(1);up(i,1,n)for(int x:E2[i])if(chk(i,x))T.modify(dfn[x],dfn[x]+siz[x]-1,1,n,1,-1); up(i,1,n)T.modify(dfn[i],dfn[i]+siz[i]-1,1,n,1,1); res=0,dfs2(1);printf("%lld\n",res); } int main(){ freopen("1.in","r",stdin),freopen("1.out","w",stdout); int t=read();while(t--)slv(); //slv(); cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }_;