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<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int t,n,a[55][55],pa[55],size[55];
queue<int>q;
struct Graph
{
	struct Edge
	{
		int to;
		int nxt;
	}e[105];
	int edgenum,head[55],pa[55],d[55];
	void add(int u,int v)
	{
		e[++edgenum].to=v;
		e[edgenum].nxt=head[u];
		head[u]=edgenum;
		d[v]++;
	}
	void dfs(int node)
	{
		for(int hd=head[node];hd;hd=e[hd].nxt)
		{
			int to=e[hd].to;
			if(to==pa[node])continue;
			pa[to]=node;
			dfs(to);
		}
	}
	bool topsort()
	{
		for(int i=1;i<=n;i++)
		  if(d[i]==0)q.push(i);
		while(!q.empty())
		{
			int node=q.front();
			q.pop();
			for(int hd=head[node];hd;hd=e[hd].nxt)
			{
				int to=e[hd].to;
				d[to]--;
				if(d[to]==0)q.push(to);
			}
		}
		for(int i=1;i<=n;i++)
		  if(d[i])return 0;
		return 1;
	}
}T1,T2,G;
int T;
int find(int x)
{
	return x==pa[x]?x:pa[x]=find(pa[x]);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)pa[i]=i,size[i]=1;
		memset(a,0,sizeof(a));
		T1.edgenum=0;
		memset(T1.head,0,sizeof(T1.head));
		memset(T1.d,0,sizeof(T1.d));
		T2.edgenum=0;
		memset(T2.head,0,sizeof(T2.head));
		memset(T2.d,0,sizeof(T2.d));
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			T1.add(u,v);
			T1.add(v,u);
			a[u][v]=a[v][u]=1;
		}
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			T2.add(u,v);
			T2.add(v,u);
			if(a[u][v])size[find(v)]+=size[find(u)],pa[find(u)]=find(v);
		}
		int ans=-1;
		for(int i=1;i<=n;i++)
		{
			if(find(i)!=i)continue;
			T1.pa[i]=T2.pa[i]=0;
			T1.dfs(i);
			T2.dfs(i);
			G.edgenum=0;
			memset(G.head,0,sizeof(G.head));
			memset(G.d,0,sizeof(G.d));
			for(int j=1;j<=n;j++)
			{
				if(find(j)!=i&&T1.pa[j]&&find(T1.pa[j])!=i) G.add(j,T1.pa[j]);
				if(find(j)!=i&&T2.pa[j]&&find(T2.pa[j])!=i) G.add(T2.pa[j],j);
			}
			if(G.topsort())ans=max(ans,size[i]);
		}
		if(ans==-1)
		{
			for(int i=1;i<=n;i++)
			{
				if(T1.d[i]!=1)continue;
				T2.pa[i]=0;
				T2.dfs(i);
				for(int j=1;j<=n;j++)
				{
					if(i==j)continue;
					T1.pa[j]=0;
					T1.dfs(j);
					G.edgenum=0;
					memset(G.head,0,sizeof(G.head));
					memset(G.d,0,sizeof(G.d));
					for(int k=1;k<=n;k++)
					{
						if(k!=i&&T1.pa[k]!=i)G.add(k,T1.pa[k]);
						if(k!=i&&T2.pa[k]!=i)G.add(T2.pa[k],k);
					}
					if(G.topsort())ans=0;
				}
			}
		}
		if(ans!=-1)printf("%d\n",n-ans);
		else printf("-1\n");
	}
	return 0;
}