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 N 52
#define IT set<int>::iterator
using namespace std;
int T,n,fa[N],fb[N];
set<int> a[N],b[N],c[N];

template <class T> inline void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}

void dfs(int rt)//跑a 
{
	for(IT i=a[rt].begin();i != a[rt].end();++i)
	{
		int v = (*i);
		if(v == fa[rt]) continue;
		fa[v] = rt;
		dfs(v);
	}
}
void DFS(int rt)
{
	for(IT i=b[rt].begin();i != b[rt].end();++i)
	{
		int v = (*i);
		if(v == fb[rt]) continue;
		fb[v] = rt;
		DFS(v);
	}
}
bool del[N];
void tx(int rt)
{
	del[rt] = 1;
	bool same[N]={0};
	for(IT i=a[rt].begin();i != a[rt].end();++i) same[*i] = 1;
	for(IT i=b[rt].begin();i != b[rt].end();++i)
	{
		int v = (*i);
		if(v == fb[rt] || !same[v]) continue;
		tx(v);
	}
}
bool vis[N];
bool cir(int rt)
{
	if(vis[rt]) return 1;
	vis[rt] = 1;
	for(IT i=c[rt].begin();i != c[rt].end();++i) if(cir(*i)) return 1;
	vis[rt] = 0;
	return 0;
}

int solve(int t)
{
	for(int i=0;i<N;++i) c[i].clear();
	memset(del,0,sizeof(del));
	memset(fa,0,sizeof(fa));
	memset(fb,0,sizeof(fb));
	dfs(t); DFS(t); tx(t);

	for(int i=1;i<=n;++i)
	{
		if(del[i]) continue;
		c[0].insert(i);
		if(!del[fa[i]]) c[fa[i]].insert(i);
		if(!del[fb[i]]) c[i].insert(fb[i]);
	}
	memset(vis,0,sizeof(vis));
	if(!cir(0))
	{
		int mn = n;
		for(int i=1;i<=n;++i) mn -= del[i];
		return mn;
	}
	return n + 1;
}

int main()
{
	read(T);
	while(T--)
	{
		for(int i=1;i<N;++i) a[i].clear();
		for(int i=1;i<N;++i) b[i].clear();
		read(n);
		for(int i=1;i<n;++i)
		{
			int x,y;
			read(x);read(y);
			a[x].insert(y);
			a[y].insert(x);
		}
		for(int i=1;i<n;++i)
		{
			int x,y;
			read(x);read(y);
			b[x].insert(y);
			b[y].insert(x);
		}
		int ans = n + 1;
		for(int t=1;t<=n;++t) ans = min(ans,solve(t));
		if(ans == n + 1)
		{
			for(int i=1;i<=n;++i)
			{
				if(a[i].size() == 1)
				for(int j=1;j<=n;++j)
				{
					if(i != j)
					{
						set<int> tp = a[i],cc = a[j],kk = a[*a[i].begin()];
						a[*a[i].begin()].erase(i);
						a[i].clear();
						a[i].insert(j);
						a[j].insert(i);
						
						if(solve(i) != n + 1)
						{
							ans = n;
							goto u;
						}
						a[i] = tp;
						a[j] = cc;
						a[*a[i].begin()]=kk;
					}
				}
			}
		}
		u:;
		printf("%d\n",ans == n + 1 ? -1 : ans);
	}
	return 0;
}
/*
2
5
1 3
2 3
3 4
4 5
3 1
1 2
2 4
4 5

5
1 2
2 3
3 4
4 5
3 1
1 2 
2 4 
4 5
*/