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<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int ans;
struct edges
{
	int to,next;
}edge[333];
int first1[55],first2[55],first3[55],now;
int d[55],d1[55];
void adde(int *first,int a,int b)
{
	now++;
	edge[now].to=b;
	edge[now].next=first[a];
	first[a]=now;
}
bool vis[55];
int fa1[55],fa2[55];
bool mk[55];
queue <int> q;
void work1(int p)
{
	vis[p]=true;
	for(int e=first1[p];e;e=edge[e].next)
		if(!vis[edge[e].to])
		{
			fa1[edge[e].to]=p;
			work1(edge[e].to);
		}
}
void work2(int p)
{
	vis[p]=true;
	for(int e=first2[p];e;e=edge[e].next)
		if(!vis[edge[e].to])
		{
			fa2[edge[e].to]=p;
			work2(edge[e].to);
		}
}
int main()
{
	int T,n,x,y,h,cnt,cnt1,p;
	bool jud;
	scanf("%d",&T);
	while(T--)
	{
		ans=214748;
		now=0;
		memset(first1,0,sizeof(first1));
		memset(first2,0,sizeof(first2));
		scanf("%d",&n);
		memset(d,0,sizeof(d));
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			adde(first1,x,y);
			adde(first1,y,x);
			d[x]++;
			d[y]++;
		}
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			adde(first2,x,y);
			adde(first2,y,x);
		}
		h=now;
		memset(vis,0,sizeof(vis));
		work1(1);
		memset(vis,0,sizeof(vis));
		work2(1);
		jud=true;
		for(int i=2;i<=n;i++)
			if(fa1[i]!=fa2[i])
				jud=false;
		if(jud)
		{
			printf("0\n");
			continue;
		}
		mk[0]=false;
		for(int i=1;i<=n;i++)
			if(d[i]==1)
			{
				memset(vis,0,sizeof(vis));
				work2(i);
				fa1[i]=fa2[i]=0;
				for(int j=1;j<=n;j++)
					if(i!=j)
					{
						memset(vis,0,sizeof(vis));
						vis[i]=true;
						work1(j);
						fa1[j]=i;
						cnt=0;
						for(int k=1;k<=n;k++)
							if(fa1[k]!=fa2[k])
							{
								mk[k]=true;
								cnt++;
							}
							else
								mk[k]=false;
						jud=false;
						for(int k=1;k<=n;k++)
							if((!mk[k])&&mk[fa1[k]])
								jud=true;
						if(jud)
							continue;
						memset(first3,0,sizeof(first3));
						now=h;
						memset(d1,0,sizeof(d1));
						for(int k=1;k<=n;k++)
							if(mk[k]&&mk[fa1[k]])
							{
								adde(first3,k,fa1[k]);
								d1[fa1[k]]++;
							}
						for(int k=1;k<=n;k++)
							if(mk[k]&&mk[fa2[k]])
							{
								adde(first3,fa2[k],k);
								d1[k]++;
							}
						cnt1=0;
						for(int k=1;k<=n;k++)
							if(mk[k]&&d1[k]==0)
								q.push(k);
						while(!q.empty())
						{
							p=q.front();
							cnt1++;
							q.pop();
							for(int e=first3[p];e;e=edge[e].next)
							{
								d1[edge[e].to]--;
								if(d1[edge[e].to]==0)
									q.push(edge[e].to);
							}
						}
						if(cnt1==cnt)
							ans=min(ans,cnt+1);
					}
			}
		if(ans==214748)
			ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}