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;
const int N=55;
int TT,n,a[N],b[N],c,d,i,j,ans,deg[N];
struct tree{
vector<int>e[N],ee[N];bool b[N];int dad[N];
inline void clear(){for(int i=1;i<=n;++i)e[i].clear();}
inline void add(int x,int y){e[x].push_back(y);e[y].push_back(x);}
inline void ini(){for(int i=1;i<=n;++i)sort(e[i].begin(),e[i].end());}
void dfs(int x,int fa,const tree&B,bool bb){
	b[x]=bb;
	for(int y:e[x])if(y!=fa)
		dfs(y,x,B,bb && binary_search(B.e[x].begin(),B.e[x].end(),y));
}
void getfa(int x,int fa){dad[x]=fa;for(int y:e[x])if(y!=fa)getfa(y,x);}
int calc(int rt,tree&B){
	int i,cnt=0;for(i=1;i<=n;++i)ee[i].clear();
	memset(b+1,0,n);dfs(rt,0,B,1);
	getfa(rt,0);B.getfa(rt,0);
	for(i=1;i<=n;++i)if(!b[i]){
		for(int j:e[i])if(j!=dad[i])ee[j].push_back(i);
		for(int j:B.e[i])if(j!=B.dad[i])ee[i].push_back(j);
	}else ++cnt;
	static int d[N],q[N];int t=0,w=0;
	memset(d+1,0,n<<2);for(i=1;i<=n;++i)for(int x:ee[i])++d[x];
	for(i=1;i<=n;++i)if(!d[i])q[++w]=i;
	for(;t<w;)for(int v:ee[q[++t]])if(!--d[v])q[++w]=v;
	return w==n?n-cnt:N;
}
}A,B,T;
int main(){
	scanf("%d",&TT);
	for(;TT--;){
		scanf("%d",&n);A.clear(),B.clear();memset(deg+1,0,n<<2);
		for(i=1;i<n;++i)scanf("%d%d",a+i,b+i),++deg[a[i]],++deg[b[i]],A.add(a[i],b[i]);
		for(i=1;i<n;++i)scanf("%d%d",&c,&d),B.add(c,d);B.ini();
		ans=N;
		for(i=1;i<=n;++i)ans=min(ans,A.calc(i,B));
		for(i=1;i<=n;++i)if(deg[i]==1){
			T.clear();for(j=1;j<n;++j)if(a[j]!=i && b[j]!=i)T.add(a[j],b[j]);
			for(j=1;j<=n;++j)if(j!=i)A=T,A.add(j,i),ans=min(ans,A.calc(i,B)+1);
		}
		if(ans==N)ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}