#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
pr pair(int x,int y){return{std::min(x,y),std::max(x,y)};}
int n;
struct treeee{
	int fir[55],deg[55],dis[110],nxt[110],id;
	void clear(){memset(fir,0,sizeof fir);memset(deg,0,sizeof deg);id=0;}
	void link(int a,int b){
		++deg[a],++deg[b];
		nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
		nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
	}
	int FA[55];
	std::vector<int>path[55];
	void DFS(int x,int fa=-1){
		if(fa==-1)path[x].clear();
		path[x].push_back(x);
		for(int i=fir[x];i;i=nxt[i]){
			if(dis[i]==fa)continue;
			FA[dis[i]]=x;
			path[dis[i]]=path[x];
			DFS(dis[i],x);
		}
	}
	bool bad[55];
	std::vector<int>G[51];
	int in[51];
	void Link(int a,int b){++in[b];G[a].push_back(b);}
	int work(const treeee&b){
		for(int i=1;i<=n;++i)G[i].clear();
		memset(in,0,sizeof in);
		for(int i=1;i<=n;++i)if(bad[i]){
			for(int j=fir[i];j;j=nxt[j])
				if(dis[j]!=FA[i])
					Link(dis[j],i);
			for(int j=b.fir[i];j;j=b.nxt[j])
				if(b.dis[j]!=b.FA[i])
					Link(i,b.dis[j]);
			}
		std::queue<int>que;int cnt=0,sum=0;
		for(int i=1;i<=n;++i)sum+=bad[i];
		for(int i=1;i<=n;++i)if(!in[i])que.push(i);
		while(que.size()){
			int x=que.front();que.pop();++cnt;
			for(int i:G[x])if(!--in[i])que.push(i);
		}
		return cnt==n?sum:1919810;
	}
}A,B,C;
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int qwq=gi();
	while(qwq--){
		n=gi();int u,v;
		std::set<pr>sa,sb;
		A.clear(),B.clear();
		for(int i=1;i<n;++i)u=gi(),v=gi(),A.link(u,v),sa.insert(pair(u,v));
		for(int i=1;i<n;++i)u=gi(),v=gi(),B.link(u,v),sb.insert(pair(u,v));
		if(sa==sb){puts("0");continue;}
		int ans=1145141;
		for(int i=1;i<=n;++i)
			if(A.deg[i]==1){
				int t=A.dis[A.fir[i]];
				B.DFS(i);
				for(int j=1;j<=n;++j){
					if(j==t||j==i)continue;
					C.clear();
					for(pr s:sa)
						if(s!=pair(i,t))C.link(s.fi,s.se);
						else C.link(i,j);
					C.DFS(i);
					for(int j=1;j<=n;++j)C.bad[j]=(B.path[j]!=C.path[j]);
					cnk(ans,C.work(B)+1);
				}
			}
		if(ans>n)ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

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<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
pr pair(int x,int y){return{std::min(x,y),std::max(x,y)};}
int n;
struct treeee{
	int fir[55],deg[55],dis[110],nxt[110],id;
	void clear(){memset(fir,0,sizeof fir);memset(deg,0,sizeof deg);id=0;}
	void link(int a,int b){
		++deg[a],++deg[b];
		nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
		nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
	}
	int FA[55];
	std::vector<int>path[55];
	void DFS(int x,int fa=-1){
		if(fa==-1)path[x].clear();
		path[x].push_back(x);
		for(int i=fir[x];i;i=nxt[i]){
			if(dis[i]==fa)continue;
			FA[dis[i]]=x;
			path[dis[i]]=path[x];
			DFS(dis[i],x);
		}
	}
	bool bad[55];
	std::vector<int>G[51];
	int in[51];
	void Link(int a,int b){++in[b];G[a].push_back(b);}
	int work(const treeee&b){
		for(int i=1;i<=n;++i)G[i].clear();
		memset(in,0,sizeof in);
		for(int i=1;i<=n;++i)if(bad[i]){
			for(int j=fir[i];j;j=nxt[j])
				if(dis[j]!=FA[i])
					Link(dis[j],i);
			for(int j=b.fir[i];j;j=b.nxt[j])
				if(b.dis[j]!=b.FA[i])
					Link(i,b.dis[j]);
			}
		std::queue<int>que;int cnt=0,sum=0;
		for(int i=1;i<=n;++i)sum+=bad[i];
		for(int i=1;i<=n;++i)if(!in[i])que.push(i);
		while(que.size()){
			int x=que.front();que.pop();++cnt;
			for(int i:G[x])if(!--in[i])que.push(i);
		}
		return cnt==n?sum:1919810;
	}
}A,B,C;
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int qwq=gi();
	while(qwq--){
		n=gi();int u,v;
		std::set<pr>sa,sb;
		A.clear(),B.clear();
		for(int i=1;i<n;++i)u=gi(),v=gi(),A.link(u,v),sa.insert(pair(u,v));
		for(int i=1;i<n;++i)u=gi(),v=gi(),B.link(u,v),sb.insert(pair(u,v));
		if(sa==sb){puts("0");continue;}
		int ans=1145141;
		for(int i=1;i<=n;++i)
			if(A.deg[i]==1){
				int t=A.dis[A.fir[i]];
				B.DFS(i);
				for(int j=1;j<=n;++j){
					if(j==t||j==i)continue;
					C.clear();
					for(pr s:sa)
						if(s!=pair(i,t))C.link(s.fi,s.se);
						else C.link(i,j);
					C.DFS(i);
					for(int j=1;j<=n;++j)C.bad[j]=(B.path[j]!=C.path[j]);
					cnk(ans,C.work(B)+1);
				}
			}
		if(ans>n)ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}

```