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<algorithm>
#include<vector>
#define pb push_back
#define forall(x,i) for (int i=0,_t=x.size();i<_t;i++)
using namespace std;

int n;
vector<int> A[55],B[55],C[55],D[55];
int fat_B[55],fat_C[55]; int tot[55];
void dfs0(int x,int f){
	fat_B[x]=f;
	forall(B[x],i){
		int v=B[x][i];
		if (v==f) continue;
		dfs0(v,x);
	}
}
void dfs1(int x,int f){
	fat_C[x]=f; tot[x]=fat_C[x]==fat_B[x];
	forall(C[x],i){
		int v=C[x][i];
		if (v==f) continue;
		dfs1(v,x);
		tot[x]+=tot[v];
	}
}
int work(int x,int y){
	//printf("work %d %d\n",x,y);
	for (int i=1;i<=n;i++) vector<int>().swap(C[i]);
	for (int i=1;i<=n;i++)
		forall(A[i],j){
			int v=A[i][j];
			if (i!=x&&v!=x) C[i].pb(v);
		}
	C[x].pb(y); C[y].pb(x);
	dfs0(x,0); dfs1(x,0);
	//puts("test");
	//for (int i=1;i<=n;i++) printf("fat %d: B %d C %d\n",i,fat_B[i],fat_C[i]);
	for (int i=1;i<=n;i++) if (tot[i]&&fat_C[i]!=fat_B[i]) return 1e9;
	//puts("valid test A passed");
	for (int i=1;i<=n;i++) vector<int>().swap(D[i]);
	int S=0;
	for (int i=1;i<=n;i++)
		if (fat_C[i]!=fat_B[i]){
			S++;
			forall(C[i],j){
				int v=C[i][j];
				if (v==fat_C[i]) continue;
				D[v].pb(i);
			}
			int v=fat_B[i];
			if (fat_C[v]!=fat_B[v]) D[v].pb(i);
		}
	//printf("S %d\n",S);
	static int que[55],hd,tl,deg[55]; hd=tl=0;
	for (int i=1;i<=n;i++) deg[i]=0;
	for (int i=1;i<=n;i++)
		forall(D[i],j) ++deg[D[i][j]];
	for (int i=1;i<=n;i++) if (fat_C[i]!=fat_B[i]&&!deg[i]) que[++tl]=i;
	while (hd<tl){
		int u=que[++hd],v;
		forall(D[u],i){
			v=D[u][i];
			if (!--deg[v]) que[++tl]=v;
		}
	}
	if (tl!=S) return 1e9;
	//puts("valid test B passed");
	return S;
}
int deg[55];
void init(){}
void solve(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		vector<int>().swap(A[i]),
		vector<int>().swap(B[i]),
		deg[i]=0;
	for (int i=1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		A[u].pb(v); A[v].pb(u);
		deg[u]++,deg[v]++;
	}
	for (int i=1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		B[u].pb(v); B[v].pb(u);
	}
	bool flg=1;
	for (int i=1;i<=n;i++){
		sort(A[i].begin(),A[i].end());
		sort(B[i].begin(),B[i].end());
		if (A[i]!=B[i]) flg=0;
	}
	if (flg) return puts("0"),void();
	int ans=1e9;
	for (int i=1;i<=n;i++) if (deg[i]==1)
		for (int j=1;j<=n;j++) if (i^j)
			ans=min(ans,work(i,j)+1);
	if (ans==1e9) puts("-1");
	else printf("%d\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while (T--) init(),solve();
	return 0;
}