#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 100010;
const int INF = 2147483600;

int T,N; 
int Node[MAXN<<1],Next[MAXN<<1],Root[MAXN+1],cnt;
int deg[MAXN+1],dg[MAXN+1];
vector<int> vec[MAXN+1],vec2[MAXN+1];

inline void insert(int u,int v,int d){
	Node[++cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt;
	deg[u]+=d;
}
inline void Ins(int u,int v){
	dg[v]++; vec2[u].push_back(v);
} int top; int vis[MAXN+1]; int tim; bool ed[61][61];
inline void dfs(int k,int Fa){
	++top; vis[k]=tim;
	for(int x=Root[k];x;x=Next[x]){
		int v=Node[x]; if(v==Fa) continue;
		if(ed[k][v]) dfs(v,k);
	} return ;
} int fa[2][MAXN+1];
inline void dfs2(int k,int Fa){
	fa[0][k]=Fa;
	for(int x=Root[k];x;x=Next[x]){
		int v=Node[x]; if(v==Fa) continue;
		dfs2(v,k);
	}
}
inline void dfs3(int k,int Fa){
	fa[1][k]=Fa;
	for(int i=0,sz=vec[k].size();i<sz;i++){
		int v=vec[k][i]; if(Fa==v) continue;
		dfs3(v,k);
	} return ;
}
inline bool check(int K){
	dfs2(K,0); dfs3(K,0); queue<int> que;
	for(int i=1;i<=N;i++) dg[i]=0,vec2[i].clear();
	for(int i=1;i<=N;i++){
		if(vis[i]!=tim){
			if(vis[fa[0][i]]!=tim) Ins(i,fa[0][i]); 
			if(vis[fa[1][i]]!=tim) Ins(fa[1][i],i);
		} 
	} for(int i=1;i<=N;i++) if(!dg[i]) que.push(i); int n=0;
	while(!que.empty()){
		int k=que.front(); que.pop(); ++n;
		for(int i=0,sz=vec2[k].size();i<sz;i++){
			dg[vec2[k][i]]--; if(!dg[vec2[k][i]]) que.push(vec2[k][i]); 
		}
	} return (n==N);
}
inline int solve(int k){
	int ret=INF;
	for(int i=1;i<=N;i++) vis[i]=0; tim=0;
	for(int i=1;i<=N;i++){
		if(!vis[i]&&(!k||k==i)) {
			++tim,top=0,dfs(i,0);
			if(check(i)) ret=min(ret,N-top);
		}
	}
	return ret;
} int U[MAXN+1],V[MAXN+1];
inline void Rebuild(int ut,int vt){
	cnt=0; for(int i=1;i<=N;i++) Root[i]=0;
	for(int i=1;i<N;i++){
		int u=U[i],v=V[i];
		if(u==ut||v==ut) insert(ut,vt,0),insert(vt,ut,0);
		else insert(u,v,0),insert(v,u,0);
	} return ;
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	T=read();
	while(T--){
		N=read(); cnt=0;
		for(int i=1;i<=N;i++) vec[i].clear(),Root[i]=0,deg[i]=dg[i]=vis[i]=0;
		for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) ed[i][j]=0;
		for(int i=1;i<N;i++){
			int u=read(),v=read();
			insert(u,v,1); insert(v,u,1);
			U[i]=u,V[i]=v;
		}
		for(int i=1;i<N;i++){
			int u=read(),v=read();
			vec[u].push_back(v);
			vec[v].push_back(u);
			ed[u][v]=ed[v][u]=1;
		} int ans=solve(0);
		for(int i=1;i<=N;i++){
			if(deg[i]==1)
				for(int j=1;j<=N;j++){
					if(i==j) continue;
					Rebuild(i,j);
					ans=min(ans,solve(i)+1);
				}
		} if(ans<INF) printf("%d\n",ans);
		else puts("-1");
	} 
	return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

Snuke has found two trees A and B, each with N vertices numbered 1 to N. The i-th edge of A connects Vertex a_i and b_i, and the j-th edge of B connects Vertex c_j and d_j. Also, all vertices of A are initially painted white.

Snuke would like to perform the following operation on A zero or more times so that A coincides with B:

* Choose a leaf vertex that is painted white. (Let this vertex be v.)
* Remove the edge incident to v, and add a new edge that connects v to another vertex.
* Paint v black.



Determine if A can be made to coincide with B, ignoring color. If the answer is yes, find the minimum number of operations required.

You are given T cases of this kind. Find the answer for each of them.

Constraints

* 1 \leq T \leq 20
* 3 \leq N \leq 50
* 1 \leq a_i,b_i,c_i,d_i \leq N
* All given graphs are trees.

Input

Input is given from Standard Input in the following format:


T
case_1
:
case_{T}


Each case is given in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

For each case, if A can be made to coincide with B ignoring color, print the minimum number of operations required, and print `-1` if it cannot.

Examples

Input

2
3
1 2
2 3
1 3
3 2
6
1 2
2 3
3 4
4 5
5 6
1 2
2 4
4 3
3 5
5 6


Output

1
-1


Input

3
8
2 7
4 8
8 6
7 1
7 3
5 7
7 8
4 2
5 2
1 2
8 1
3 2
2 6
2 7
4
1 2
2 3
3 4
3 4
2 1
3 2
9
5 3
4 3
9 3
6 8
2 3
1 3
3 8
1 7
4 1
2 8
9 6
3 6
3 5
1 8
9 7
1 6


Output

6
0
7

### Response

```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 100010;
const int INF = 2147483600;

int T,N; 
int Node[MAXN<<1],Next[MAXN<<1],Root[MAXN+1],cnt;
int deg[MAXN+1],dg[MAXN+1];
vector<int> vec[MAXN+1],vec2[MAXN+1];

inline void insert(int u,int v,int d){
	Node[++cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt;
	deg[u]+=d;
}
inline void Ins(int u,int v){
	dg[v]++; vec2[u].push_back(v);
} int top; int vis[MAXN+1]; int tim; bool ed[61][61];
inline void dfs(int k,int Fa){
	++top; vis[k]=tim;
	for(int x=Root[k];x;x=Next[x]){
		int v=Node[x]; if(v==Fa) continue;
		if(ed[k][v]) dfs(v,k);
	} return ;
} int fa[2][MAXN+1];
inline void dfs2(int k,int Fa){
	fa[0][k]=Fa;
	for(int x=Root[k];x;x=Next[x]){
		int v=Node[x]; if(v==Fa) continue;
		dfs2(v,k);
	}
}
inline void dfs3(int k,int Fa){
	fa[1][k]=Fa;
	for(int i=0,sz=vec[k].size();i<sz;i++){
		int v=vec[k][i]; if(Fa==v) continue;
		dfs3(v,k);
	} return ;
}
inline bool check(int K){
	dfs2(K,0); dfs3(K,0); queue<int> que;
	for(int i=1;i<=N;i++) dg[i]=0,vec2[i].clear();
	for(int i=1;i<=N;i++){
		if(vis[i]!=tim){
			if(vis[fa[0][i]]!=tim) Ins(i,fa[0][i]); 
			if(vis[fa[1][i]]!=tim) Ins(fa[1][i],i);
		} 
	} for(int i=1;i<=N;i++) if(!dg[i]) que.push(i); int n=0;
	while(!que.empty()){
		int k=que.front(); que.pop(); ++n;
		for(int i=0,sz=vec2[k].size();i<sz;i++){
			dg[vec2[k][i]]--; if(!dg[vec2[k][i]]) que.push(vec2[k][i]); 
		}
	} return (n==N);
}
inline int solve(int k){
	int ret=INF;
	for(int i=1;i<=N;i++) vis[i]=0; tim=0;
	for(int i=1;i<=N;i++){
		if(!vis[i]&&(!k||k==i)) {
			++tim,top=0,dfs(i,0);
			if(check(i)) ret=min(ret,N-top);
		}
	}
	return ret;
} int U[MAXN+1],V[MAXN+1];
inline void Rebuild(int ut,int vt){
	cnt=0; for(int i=1;i<=N;i++) Root[i]=0;
	for(int i=1;i<N;i++){
		int u=U[i],v=V[i];
		if(u==ut||v==ut) insert(ut,vt,0),insert(vt,ut,0);
		else insert(u,v,0),insert(v,u,0);
	} return ;
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	T=read();
	while(T--){
		N=read(); cnt=0;
		for(int i=1;i<=N;i++) vec[i].clear(),Root[i]=0,deg[i]=dg[i]=vis[i]=0;
		for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) ed[i][j]=0;
		for(int i=1;i<N;i++){
			int u=read(),v=read();
			insert(u,v,1); insert(v,u,1);
			U[i]=u,V[i]=v;
		}
		for(int i=1;i<N;i++){
			int u=read(),v=read();
			vec[u].push_back(v);
			vec[v].push_back(u);
			ed[u][v]=ed[v][u]=1;
		} int ans=solve(0);
		for(int i=1;i<=N;i++){
			if(deg[i]==1)
				for(int j=1;j<=N;j++){
					if(i==j) continue;
					Rebuild(i,j);
					ans=min(ans,solve(i)+1);
				}
		} if(ans<INF) printf("%d\n",ans);
		else puts("-1");
	} 
	return 0;
}
```