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 <cstring>
#include <queue>
#define N 52
using namespace std;
struct edge{
	int u,v;
}e[N];
int head[N],ver[N*N],nxt[N*N],l;
int head1[N],ver1[N*2],nxt1[N*2],l1;
int t,n,i,j,k,fa[N],fb[N],d[N],d1[N],cnt;
bool vis[N];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
void insert(int x,int y)
{
	l++;
	ver[l]=y;
	nxt[l]=head[x];
	head[x]=l;
}
void insert1(int x,int y)
{
	l1++;
	ver1[l1]=y;
	nxt1[l1]=head1[x];
	head1[x]=l1;
}
void dfsa(int x,int pre)
{
	fa[x]=pre;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y!=pre) dfsa(y,x);
	}
}
void dfsb(int x,int pre)
{
	fb[x]=pre;
	vis[x]=vis[pre]&(fa[x]==fb[x]);
	for(int i=head1[x];i;i=nxt1[i]){
		int y=ver1[i];
		if(y!=pre) dfsb(y,x);
	}
}
bool toposort()
{
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(d1[i]==0){
			q.push(i);
		}
	}
	int cnt=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		cnt++;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			d1[y]--;
			if(d1[y]==0) q.push(y);
		}
	}
	return (cnt==n);
}
bool check1()
{
	for(int i=1;i<=n;i++){
		if(fa[i]!=fb[i]) return 0;
	}
	return 1;
}
int check(int root)
{
	memset(vis,0,sizeof(vis));vis[0]=1;
	for(int i=1;i<n;i++){
		if(e[i].u!=root&&e[i].v!=root) insert(e[i].u,e[i].v),insert(e[i].v,e[i].u);
	}
	dfsa(root,0);dfsb(root,0);
	memset(head,0,sizeof(head));l=0;
	memset(d1,0,sizeof(d1));
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			if(!vis[fa[i]]) insert(i,fa[i]),d1[fa[i]]++;
			if(!vis[fb[i]]) insert(fb[i],i),d1[i]++;
			ans++;
		}
	}
	if(toposort()) return ans;
	else return 1<<30;
}
int main()
{
	t=read();
	while(t--){
		cnt++;
		int ans=1<<30;
		memset(d,0,sizeof(d));
		memset(head1,0,sizeof(head1));l1=0;
		memset(head,0,sizeof(head));l=0;
		n=read();
		for(i=1;i<n;i++){
			e[i].u=read();e[i].v=read();
			d[e[i].u]++;d[e[i].v]++;
			insert(e[i].u,e[i].v);insert(e[i].v,e[i].u);
		}
		for(i=1;i<n;i++){
			int u=read(),v=read();
			insert1(u,v);insert1(v,u);
		}
		dfsa(1,0);dfsb(1,0);
		if(check1()){
			puts("0");
			continue;
		}
		for(i=1;i<=n;i++){
			if(d[i]==1){
				for(j=1;j<=n;j++){
					if(i==j) continue;
					memset(head,0,sizeof(head));l=0;
					insert(i,j);insert(j,i);
					ans=min(ans,check(i));
				}
			}
		}
		if(ans!=1<<30) printf("%d\n",ans+1);
		else puts("-1");
	}
	return 0;
}