#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=60,inf=1e9;
struct xxx{
	int y,nxt,mark;
};
int mark[N],d[N],vis[N];
int n,m,ban,ans,T;
struct Tree{/*{{{*/
	xxx a[N*2];
	int h[N],pre[N];
	int tot;
	void init(){
		memset(h,-1,sizeof(h));
		memset(pre,-1,sizeof(pre));
		tot=0;
	}
	void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot; a[tot].mark=0;}
	void dfs(int fa,int x){
		int u;
		pre[x]=fa;
		for (int i=h[x];i!=-1;i=a[i].nxt){
			u=a[i].y;
			if (u==fa||u==ban) continue;
			dfs(x,u);
		}
	}
}ta,tb;/*}}}*/
namespace G{/*{{{*/
	xxx a[N*2];
	int h[N],inst[N],vis[N];
	int tot;
	void init(){
		memset(h,-1,sizeof(h));
		tot=0;
	}
	void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;/*printf("%d %d\n",x,y);*/}
	bool dfs(int x){
		int u;
		inst[x]=1; vis[x]=1;
		for (int i=h[x];i!=-1;i=a[i].nxt){
			u=a[i].y;
			if (!vis[u]){
				if (!dfs(u)) return false;
			}
			else if (inst[u])
				return false;
		}
		inst[x]=0;
		return true;
	}
	bool NoCir(){
		memset(vis,0,sizeof(vis));
		memset(inst,0,sizeof(inst));
		for (int i=1;i<=n;++i)
			if (!vis[i])
				if (!dfs(i)) return false;
		return true;
	}
}/*}}}*/
int Tm;
void dfs(int fa,int x){
	int u,tm;
	tm=++Tm;
	vis[x]=1;
	for (int i=ta.h[x];i!=-1;i=ta.a[i].nxt) mark[ta.a[i].y]=tm;
	for (int i=tb.h[x];i!=-1;i=tb.a[i].nxt){
		u=tb.a[i].y;
		if (u==fa||u==ban||mark[u]!=tm) continue;
		dfs(x,u);
	}
}
int solve(int rt){
	int ret=0;
	G::init();
	ban=rt;
	memset(ta.pre,0,sizeof(ta.pre));
	ta.dfs(0,rt);
	memset(tb.pre,0,sizeof(tb.pre));
	tb.dfs(0,rt);

	memset(vis,0,sizeof(vis));
	dfs(0,rt);

	for (int i=1;i<=n;++i){
		if (vis[i]) continue;
		if (!vis[ta.pre[i]]) 
			G::add(i,ta.pre[i]);
		if (!vis[tb.pre[i]]) 
			G::add(tb.pre[i],i);
		++ret;
	}
	if (!G::NoCir()) return inf;
	return ret;
}
void Solve(){
	ans=inf;
	for (int i=1;i<=n;++i) 
		ans=min(ans,solve(i));
	int tmp;
	for (int i=1;i<=n;++i){
		if (d[i]!=1) continue;
		for (int j=1;j<=n;++j){
			if (i==j||j==ta.a[ta.h[i]].y) continue;
			tmp=ta.a[ta.h[i]].y;
			ta.a[ta.h[i]].y=j;
			int ttmp=ans;
			ans=min(ans,solve(i)+1);
			if (ttmp!=ans&&ans==1)
				int debug=1;
			ta.a[ta.h[i]].y=tmp;
		}
	}
	if (ans==inf) ans=-1;
	printf("%d\n",ans);
}
void init(){
	ta.init();
	tb.init();
	memset(d,0,sizeof(d));
}

int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
#endif
	int x,y;
	scanf("%d",&T);
	for (int o=1;o<=T;++o){
		scanf("%d",&n);
		init();
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			ta.add(x,y); ta.add(y,x);
			++d[x]; ++d[y];
		}
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			tb.add(x,y); tb.add(y,x);
		}
		Solve();
	}
}
### Prompt

Create a solution in CPP for 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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=60,inf=1e9;
struct xxx{
	int y,nxt,mark;
};
int mark[N],d[N],vis[N];
int n,m,ban,ans,T;
struct Tree{/*{{{*/
	xxx a[N*2];
	int h[N],pre[N];
	int tot;
	void init(){
		memset(h,-1,sizeof(h));
		memset(pre,-1,sizeof(pre));
		tot=0;
	}
	void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot; a[tot].mark=0;}
	void dfs(int fa,int x){
		int u;
		pre[x]=fa;
		for (int i=h[x];i!=-1;i=a[i].nxt){
			u=a[i].y;
			if (u==fa||u==ban) continue;
			dfs(x,u);
		}
	}
}ta,tb;/*}}}*/
namespace G{/*{{{*/
	xxx a[N*2];
	int h[N],inst[N],vis[N];
	int tot;
	void init(){
		memset(h,-1,sizeof(h));
		tot=0;
	}
	void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;/*printf("%d %d\n",x,y);*/}
	bool dfs(int x){
		int u;
		inst[x]=1; vis[x]=1;
		for (int i=h[x];i!=-1;i=a[i].nxt){
			u=a[i].y;
			if (!vis[u]){
				if (!dfs(u)) return false;
			}
			else if (inst[u])
				return false;
		}
		inst[x]=0;
		return true;
	}
	bool NoCir(){
		memset(vis,0,sizeof(vis));
		memset(inst,0,sizeof(inst));
		for (int i=1;i<=n;++i)
			if (!vis[i])
				if (!dfs(i)) return false;
		return true;
	}
}/*}}}*/
int Tm;
void dfs(int fa,int x){
	int u,tm;
	tm=++Tm;
	vis[x]=1;
	for (int i=ta.h[x];i!=-1;i=ta.a[i].nxt) mark[ta.a[i].y]=tm;
	for (int i=tb.h[x];i!=-1;i=tb.a[i].nxt){
		u=tb.a[i].y;
		if (u==fa||u==ban||mark[u]!=tm) continue;
		dfs(x,u);
	}
}
int solve(int rt){
	int ret=0;
	G::init();
	ban=rt;
	memset(ta.pre,0,sizeof(ta.pre));
	ta.dfs(0,rt);
	memset(tb.pre,0,sizeof(tb.pre));
	tb.dfs(0,rt);

	memset(vis,0,sizeof(vis));
	dfs(0,rt);

	for (int i=1;i<=n;++i){
		if (vis[i]) continue;
		if (!vis[ta.pre[i]]) 
			G::add(i,ta.pre[i]);
		if (!vis[tb.pre[i]]) 
			G::add(tb.pre[i],i);
		++ret;
	}
	if (!G::NoCir()) return inf;
	return ret;
}
void Solve(){
	ans=inf;
	for (int i=1;i<=n;++i) 
		ans=min(ans,solve(i));
	int tmp;
	for (int i=1;i<=n;++i){
		if (d[i]!=1) continue;
		for (int j=1;j<=n;++j){
			if (i==j||j==ta.a[ta.h[i]].y) continue;
			tmp=ta.a[ta.h[i]].y;
			ta.a[ta.h[i]].y=j;
			int ttmp=ans;
			ans=min(ans,solve(i)+1);
			if (ttmp!=ans&&ans==1)
				int debug=1;
			ta.a[ta.h[i]].y=tmp;
		}
	}
	if (ans==inf) ans=-1;
	printf("%d\n",ans);
}
void init(){
	ta.init();
	tb.init();
	memset(d,0,sizeof(d));
}

int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
#endif
	int x,y;
	scanf("%d",&T);
	for (int o=1;o<=T;++o){
		scanf("%d",&n);
		init();
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			ta.add(x,y); ta.add(y,x);
			++d[x]; ++d[y];
		}
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			tb.add(x,y); tb.add(y,x);
		}
		Solve();
	}
}
```