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<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=55,INF=1000010000;
int cas,n,u,v,o,cnt,rt;
int a[N][N],b[N][N],c[N],t[N];
queue<int>q;
struct graph{
	int f[N],d[N];
	vector<int>ve[N];
	void clr(){FOR(i,0,N-1) ve[i].clear(),d[i]=f[i]=0;}
	void add(int u,int v){ve[u].push_back(v),d[v]++;}
	void del(int u,int v){ve[u].pop_back();  d[v]--;}
	void dfa(int u){
		for(int v:ve[u])if(v!=f[u] && a[u][v])
			f[v]=u,c[v]=c[u]|!(a[u][v]&b[u][v]),dfa(v);
	}
	void dfb(int u){
		for(int v:ve[u])if(v!=f[u] && b[u][v])
			f[v]=u,c[v]=c[u]|!(a[u][v]&b[u][v]),dfb(v);
	}
	int top(){
		int sum=0;
		FOR(i,1,n)if(c[i] && !d[i]) q.push(i);
		while(q.size()){
			u=q.front();q.pop();sum++;
			for(int v:ve[u])if(!--d[v]) q.push(v);
		}
		return sum;
	}
}A,B,G;
int chk(int r){
	a[rt][o]=a[o][rt]=0;
	a[rt][r]=a[r][rt]=1;
	A.add(rt,r);A.add(r,rt);
	FOR(i,1,n) A.f[i]=B.f[i]=c[i]=0;
	A.dfa(rt);B.dfb(rt);
	cnt=0;G.clr();
	FOR(i,1,n)if(c[i]){
		cnt++;
		if(c[A.f[i]]) G.add(i,A.f[i]);
		if(c[B.f[i]]) G.add(B.f[i],i);
	}
	a[rt][o]=a[o][rt]=1;
	a[rt][r]=a[r][rt]=0;
	A.del(rt,r);A.del(r,rt);
	return G.top()==cnt?cnt:INF;
}
int work(){
	scanf("%d",&n);
	FOR(i,2,n) scanf("%d%d",&u,&v),A.add(u,v),A.add(v,u),a[u][v]=a[v][u]=1,t[u]=v,t[v]=u;
	FOR(i,2,n) scanf("%d%d",&u,&v),B.add(u,v),B.add(v,u),b[u][v]=b[v][u]=1;
	FOR(i,1,n) A.f[i]=B.f[i]=c[i]=0;rt=0;
	A.dfa(1);B.dfb(1);
	int ret=0;
	FOR(i,1,n)if(c[i]) ret=INF;
	FOR(i,1,n)if(A.d[i]==1)FOR(j,1,n)if(j!=i && j!=t[i])
		rt=i,o=t[i],ret=min(ret,chk(j)+1);
	A.clr();B.clr();
	FOR(i,1,n)FOR(j,1,n) a[i][j]=b[i][j]=0;
	return ret==INF?-1:ret;
}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d",&cas);
	while(cas--) cout<<work()<<'\n';
}