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>
#define PB push_back
#define MP std::make_pair
#define FI first
#define SE second
#define M 1000005
#define INF 1000000000
int t,n,faA[M],faB[M];
std::vector <int> EdgeA[M],EdgeB[M],tmp[M],G[M];
bool flag[M];
int read(){
	char c=getchar();int ans=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
	return ans;
}
void Write(int x){
	if (x<0) putchar('-'),x=-x;
	if (x<10) putchar(x+'0');
	else Write(x/10),putchar(x%10+'0');
	return;
}
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
void DFS_A(int x,int f){
	faA[x]=f;
	for (auto i:tmp[x])
		if (i!=f) DFS_A(i,x);
	return;
}
void DFS_B(int x,int f){
	faB[x]=f;
	for (auto i:EdgeB[x])
		if (i!=f) DFS_B(i,x);
	return;
}
bool topo_sort(){
	std::queue <int> Q;
	int cnt=0;static int deg[M];
	for (int i=1;i<=n;i++) deg[i]=0,cnt+=flag[i];
	for (int i=1;i<=n;i++)
		for (auto j:G[i]) deg[j]++;
	for (int i=1;i<=n;i++)
		if (flag[i]&&!deg[i]) Q.push(i),--cnt;
	while (!Q.empty()){
		int now=Q.front();Q.pop();
		for (auto j:G[now])
			if (!--deg[j]) Q.push(j),--cnt;
	}
	return !cnt;
}
int check(int x,int y){
	if (EdgeA[x][0]==y) return INF;
	int ans=0;
	for (int i=1;i<=n;i++)
		for (auto j:EdgeA[i])
			if (!(i==x&&j==EdgeA[x][0])&&!(i==EdgeA[x][0]&&j==x)) tmp[i].PB(j),tmp[j].PB(i);
	tmp[x].PB(y),tmp[y].PB(x),DFS_A(x,0),DFS_B(x,0);
	for (int i=1;i<=n;i++) ans+=(flag[i]=(faA[i]!=faB[i]));
	for (int i=1;i<=n;i++)
		if (faA[i]&&flag[faA[i]]&&!flag[i]) return INF;
	for (int i=1;i<=n;i++)
		if (faA[i]&&flag[i]&&flag[faA[i]]) G[i].PB(faA[i]);
	for (int i=1;i<=n;i++)
		if (faB[i]&&flag[i]&&flag[faB[i]]) G[faB[i]].PB(i);
	return topo_sort()?ans:INF;
}
int main(){
	t=read();
	while (t--){
		n=read();int ans=INF;bool flag=1;
		for (int i=1,u,v;i<n;i++) u=read(),v=read(),EdgeA[u].PB(v),EdgeA[v].PB(u);
		for (int i=1,u,v;i<n;i++) u=read(),v=read(),EdgeB[u].PB(v),EdgeB[v].PB(u);
		for (int i=1;i<=n;i++){
			std::sort(EdgeA[i].begin(),EdgeA[i].end());
			std::sort(EdgeB[i].begin(),EdgeB[i].end());
			flag&=(EdgeA[i]==EdgeB[i]);
		}
		if (flag) printf("0\n");
		else {
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++)
					if (EdgeA[i].size()==1){
						ans=min(ans,check(i,j)+1);
						for (int i=1;i<=n;i++) G[i].clear(),tmp[i].clear();
					}
			Write(ans==INF?-1:ans),putchar('\n');
		}
		for (int i=1;i<=n;i++) EdgeA[i].clear(),EdgeB[i].clear();
	}
	return 0;
}