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<stdio.h>
#include<queue>
using namespace std;
int head2[64],last2[128],to2[128],cnt2=0;
void add2(int u,int v)
{
	cnt2++;
	last2[cnt2]=head2[u];
	head2[u]=cnt2;
	to2[cnt2]=v;
}
int fa2[64];
void dfs2(int u,int f)
{
	fa2[u]=f;
	for(int i=head2[u];i;i=last2[i])
	{
		int v=to2[i];
		if(v==f)
		{
			continue;
		}
		dfs2(v,u);
	}
}
int head1[64],last1[128],to1[128],cnt1=0;
void add1(int u,int v)
{
	cnt1++;
	last1[cnt1]=head1[u];
	head1[u]=cnt1;
	to1[cnt1]=v;
}
int fa1[64];
void dfs1(int u,int f)
{
	fa1[u]=f;
	for(int i=head1[u];i;i=last1[i])
	{
		int v=to1[i];
		if(v==f)
		{
			continue;
		}
		dfs1(v,u);
	}
}
int a[64],b[64];
int deg[64];
int head[64],last[128],to[128],d[128],cnt=0;
void add(int u,int v)
{
	cnt++;
	last[cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	d[v]++;
}
queue<int> q;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			head1[i]=0;
			head2[i]=0;
			deg[i]=0;
		}
		cnt1=0;
		cnt2=0;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&a[i],&b[i]);
			deg[a[i]]++;
			deg[b[i]]++;
			add1(a[i],b[i]);
			add1(b[i],a[i]);
		}
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add2(u,v);
			add2(v,u);
		}
		dfs1(1,0);
		dfs2(1,0);
		bool ok=true;
		for(int i=1;i<=n;i++)
		{
			if(fa1[i]!=fa2[i])
			{
				ok=false;
				break;
			}
		}
		if(ok)
		{
			printf("0\n");
			continue;
		}
		int ans=n+1;
		for(int i=1;i<n;i++)
		{
			if(deg[b[i]]==1)
			{
				int t=a[i];
				a[i]=b[i];
				b[i]=t;
			}
			if(deg[a[i]]>1)
			{
				continue;
			}
			for(int j=1;j<=n;j++)
			{
				if(j==a[i])
				{
					continue;
				}
				cnt1=0;
				for(int k=1;k<=n;k++)
				{
					head1[k]=0;
				}
				for(int k=1;k<n;k++)
				{
					if(k==i)
					{
						continue;
					}
					add1(a[k],b[k]);
					add1(b[k],a[k]);
				}
				add1(a[i],j);
				dfs1(a[i],0);
				dfs2(a[i],0);
				int ans2=1;
				for(int k=1;k<=n;k++)
				{
					d[k]=0;
					head[k]=0;
				}
				cnt=0;
				for(int k=1;k<=n;k++)
				{
					if(k==a[i])
					{
						continue;
					}
					if(fa1[k]==fa2[k])
					{
						if(fa1[fa1[k]]!=fa2[fa2[k]])
						{
							ans2=n+1;
							break;
						}
					}
					else
					{
						ans2++;
						if(fa1[fa1[k]]!=fa2[fa1[k]])
						{
							add(k,fa1[k]);
						}
						if(fa1[fa2[k]]!=fa2[fa2[k]])
						{
							add(fa2[k],k);
						}
					}
				}
				if(ans2>=ans)
				{
					continue;
				}
				int rm=ans2-1;
				for(int i=1;i<=n;i++)
				{
					if(fa1[i]==fa2[i])
					{
						continue;
					}
					if(d[i]==0)
					{
						q.push(i);
					}
				}
				while(!q.empty())
				{
					int u=q.front();
					q.pop();
					rm--;
					for(int i=head[u];i;i=last[i])
					{
						int v=to[i];
						d[v]--;
						if(d[v]==0)
						{
							q.push(v);
						}
					}
				}
				if(!rm)
				{
					ans=ans2;
				}
			}
		}
		if(ans>n)
		{
			ans=-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}