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

Solution (in CPP):

Solution:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=105;
int h[N][2],n,rd[N],h2[N][2],mrk[N],T,Ans,tag[N];
vector<int> w1[N],w2[N];
struct graph{
	int t,w[N],ne[N],la[N],rd[N];
	void link(int x,int y){
		w[++t]=y;
		ne[t]=la[x];
		la[x]=t;
		rd[y]++;
	}
	void clear(){
		for (int i=1;i<=n;i++)la[i]=rd[i]=0;
		t=0;
	}
	int go(){
		vector<int> d;
		for (int i=1;i<=n;i++)
			if (!rd[i])d.push_back(i);
		for (int i=0;i<d.size();i++){
			int x=d[i];
			for (int y=la[x];y;y=ne[y]){
				int z=w[y];
				if (!--rd[z])d.push_back(z);
			}
		}
		clear();
		return d.size()==n;
	}
}G;
void dfs(int x,int fa,vector<int> *w,int rev){
	if (!tag[x]&&!tag[fa]){
		if (!rev)G.link(x,fa);
		else G.link(fa,x);
	}
	for (int z:w[x])
		if (z!=fa)dfs(z,x,w,rev);
}
void check(int x,int ans){
	static int d[N],l,r;
	for (int i=1;i<=n;i++)mrk[i]=tag[i]=0,w1[i].clear(),w2[i].clear();
	l=0,r=1;d[1]=x;
	for (int i=1;i<n;i++){
		int x=h[i][0],y=h[i][1];
		w1[x].push_back(y);
		w1[y].push_back(x);
		x=h2[i][0],y=h2[i][1];
		w2[x].push_back(y);
		w2[y].push_back(x);
	}tag[x]=1;
	while (l<r){
		int x=d[++l];
		for (auto z:w1[x])
			if (!tag[z])mrk[z]=x;
		for (auto z:w2[x])
			if (mrk[z]==x)d[++r]=z,tag[z]=1;
	}
	ans-=r;
	dfs(x,0,w1,0);
	dfs(x,0,w2,1);
	if (G.go())Ans=min(Ans,ans);
}
int main(){
	for (cin>>T;T--;){
		cin>>n;
		Ans=n+1;
		for (int i=1;i<=n;i++)rd[i]=0;
		for (int i=1;i<n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			h[i][0]=x,h[i][1]=y;
			rd[x]++,rd[y]++;
		}
		for (int i=1;i<n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			h2[i][0]=x,h2[i][1]=y;
		}
		for (int i=1;i<=n;i++){
			if (rd[i]!=1){
				check(i,n);
				continue;
			}
			int z=0,q=0,x;
			for (int j=1;j<n;j++)
				if (h[j][0]==i||h[j][1]==i)z=j,q=h[j][0]==i;
			for (int j=1;j<=n;j++){
				if (i==j)continue;
				x=h[z][q];
				h[z][q]=j;
				check(i,(x!=j)+n);
				h[z][q]=x;
			}
		}
		cout<<(Ans>n?-1:Ans)<<endl;
	}
}