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;

int RT;

struct tr{
	int la[105],nt[205],en[205],owo;
	void adg(int x,int y) {
		en[++owo]=y; nt[owo]=la[x]; la[x]=owo;
	}
	void re() {
		memset(la,0,sizeof la); owo = 0;
	}
	int fa[105];
	void dfs(int x,int ba) {
		fa[x] = ba;
		for(int it=la[x];it;it=nt[it]) {
			int y = en[it];
			if(y==ba||y==RT) continue;
			dfs(y,x);
		}
	}
}A,B;
int en[205],la[105],nt[205],owo;
void adg(int x,int y) {
	en[++owo]=y; nt[owo]=la[x]; la[x]=owo;
}
bool vis[105];
bool inst[105];

int ANS;
int n,ds[105];
bool dds(int x) {
	inst[x] = 1;
	vis[x] = 1;
	for(int it=la[x];it;it=nt[it]) {
		int y = en[it];
		if(inst[y]) return 0;
		else if(!vis[y]){
			if(!dds(y)) return 0;
		}
	}
	inst[x] = 0;
	return 1;
}
int MKT;
int mark[105];
bool V[105];
void DC(int x,int ba) {
	V[x] = 1;
	int yo = ++MKT;
	for(int it=A.la[x];it;it=A.nt[it]) mark[A.en[it]] = yo;
	for(int it=B.la[x];it;it=B.nt[it]) {
		int y = B.en[it];
		if(y==ba||y==RT) continue;
		if(mark[y]==yo) DC(y,x);
	}
}
void rre() {
	memset(la,0,sizeof la); owo = 0;
	memset(vis,0,sizeof vis);
	memset(inst,0,sizeof inst);
	memset(V,0,sizeof V);
}
int orz(int xx) {
	RT = xx;
	for(int i=1;i<=n;i++) {
		A.fa[i] = B.fa[i] = 0;
	}
	A.dfs(xx,0); B.dfs(xx,0);
	rre();

	DC(xx,0);
	int cc = 0;
	for(int i=1;i<=n;i++) {
		if(V[i]) continue;
		if(!V[A.fa[i]]) adg(i,A.fa[i]);
		if(!V[B.fa[i]]) adg(B.fa[i],i);
		cc++;
	}
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue;
		if(!dds(i)) return 0x3f3f3f3f;
	}
	return cc;
}
void solve() {
	scanf("%d",&n);
	A.re(); B.re();
	ANS = 0x3f3f3f3f;
	memset(ds,0,sizeof ds);
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		A.adg(x,y);A.adg(y,x);
		ds[x]++; ds[y]++;
	}
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		B.adg(x,y);B.adg(y,x);
	}
	for(int i=1;i<=n;i++) 
		ANS = min(ANS,orz(i));
	for(int i=1;i<=n;i++) {
		if(ds[i]==1) {
			int ff = A.en[A.la[i]];
			for(int j=1;j<=n;j++) {
				if(j!=i&&j!=ff) {
					A.en[A.la[i]] = j;
					ANS = min(ANS,orz(i)+1);
					A.en[A.la[i]] = ff;
				} 
			}
		}
	}
	if(ANS==0x3f3f3f3f) puts("-1");
	else printf("%d\n",ANS);
}

int main() {
	int T;
	scanf("%d",&T);
	while(T--) solve();
}