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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55,p=1000000007,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int T,n,ans,deg[N],u[N],v[N],h[N][N],inq[N],fa[N];
struct tree{
	vector<int> e[N];
	void clear(){for (int i=1;i<=n;i++) e[i].clear();}
	void add(int u,int v){e[u].push_back(v);e[v].push_back(u);}
	void work(int x,int fath,int *fa){
		fa[x]=fath;
		for (auto y : e[x])
		if (y!=fath) work(y,x,fa);
	}
}a,b,c;
struct graph{
	int h[N];
	vector<int> e[N];
	void clear(){for (int i=1;i<=n;i++) e[i].clear();}
	void add(int u,int v){e[u].push_back(v);}
	bool work(int x){
		h[x]=1;
		for (auto y : e[x])
		if (h[y]<2){
			if (h[y]) return false;
			else if (!work(y)) return false;
		}
		h[x]=2;return true;
	}
	bool check(){
		memset(h,0,sizeof(h));
		for (int i=1;i<=n;i++)
		if ((!h[i])&&(!work(i))) return false;
		return true;
	}
}g;
int check(int root){
	a.clear();c.clear();g.clear();
	for (int i=1;i<n;i++){
		a.add(u[i],v[i]);
		if (h[u[i]][v[i]]) c.add(u[i],v[i]);
	}
	memset(inq,0,sizeof(inq));
	c.work(root,-1,inq);
	a.work(root,0,fa);
	for (int i=1;i<=n;i++)
	if ((!inq[i])&&(!inq[fa[i]])) g.add(i,fa[i]);
	b.work(root,0,fa);
	for (int i=1;i<=n;i++)
	if ((!inq[i])&&(!inq[fa[i]])) g.add(fa[i],i);
	if (!g.check()) return inf;
	int t=0;
	for (int i=1;i<=n;i++) t+=(inq[i]==0);
	return t;
}
int main(){
	T=read();
	while(T--){
		b.clear();
		memset(h,0,sizeof(h));
		memset(deg,0,sizeof(deg));
		n=read();
		for (int i=1;i<n;i++){
			u[i]=read();v[i]=read();
			deg[u[i]]++;deg[v[i]]++;
		}
		for (int i=1;i<n;i++){
			int u=read(),v=read();
			b.add(u,v);h[u][v]=h[v][u]=1;
		}
		ans=check(1);
		for (int i=1;i<n;i++){
			int tu=u[i],tv=v[i];
			if (deg[tu]==1){
				for (v[i]=1;v[i]<=n;v[i]++)
				if(v[i]!=tu) ans=min(ans,check(tu)+1);
				v[i]=tv;
			}
			if (deg[tv]==1){
				for (u[i]=1;u[i]<=n;u[i]++)
				if(u[i]!=tv) ans=min(ans,check(tv)+1);
				u[i]=tu;
			}
		}
		printf("%d\n",(ans<=n) ? ans : -1);
	}
	return 0;
}