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 n,ans;
struct Graph { 
	int head[N],deg[N],fa[N],ce;
	struct edge{ int to,nxt; } e[N<<1];
	void clearGraph() { memset(head,0,sizeof(head)), memset(deg,0,sizeof(deg)); ce=0; }
	void lnk(int a,int b) { e[++ce]=(edge){b,head[a]}, head[a]=ce, ++deg[b]; }
	void dfs(int u,int lst) {
		fa[u]=lst;
		for(int i=head[u];i;i=e[i].nxt) {
			int v=e[i].to;
			if(v == lst) continue;
			dfs(v,u);
		}
	}
}A,B,D;

int remove() {
	D.clearGraph();
	int res=0,cnt=0;
	for(int i=1;i<=n;++i)
		if(A.fa[i] == B.fa[i]) {
			if(A.fa[A.fa[i]] != B.fa[B.fa[i]]) return 1e9;
		}
		else {
			++res;
			if(A.fa[A.fa[i]] != B.fa[A.fa[i]]) D.lnk(i,A.fa[i]);
			if(A.fa[B.fa[i]] != B.fa[B.fa[i]]) D.lnk(B.fa[i],i);
		}
	queue<int> q;
	for(int i=1;i<=n;++i)
		if(!D.deg[i]) q.push(i), ++cnt;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=D.head[u];i;i=D.e[i].nxt) {
			int v=D.e[i].to;
			if(!--D.deg[v]) q.push(v), ++cnt;
		}
	}
	if(cnt == n) return res;
	return 1e9;
}
int main() {
	int T; scanf("%d",&T);
	while(T--) {
		scanf("%d",&n); ans=1e9;
		A.clearGraph(), B.clearGraph();
		for(int i=2,a,b;i<=n;++i)
			scanf("%d%d",&a,&b), A.lnk(a,b), A.lnk(b,a);
		for(int i=2,c,d;i<=n;++i)
			scanf("%d%d",&c,&d), B.lnk(c,d), B.lnk(d,c);
		for(int i=1;i<=n;++i) {
			A.dfs(i,0), B.dfs(i,0), ans=min(ans,remove());
			if(A.deg[i] != 1) continue;
			for(int j=1;j<=n;++j) {
				if(i == j) continue;
				A.dfs(j,i), A.fa[i]=0, ans=min(ans,remove()+1);
			}
		}
		if(ans == 1e9) puts("-1");
		else printf("%d\n",ans);
	}
	return 0;
}