/****************************************************************
*	Author: huhao
*	Email: 826538400@qq.com
*	Create time: 2020-03-20 08:32:35
****************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
	int r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=(r<<3)+(r<<1)+(c^48);
		c=getchar();
	}
	return r*t;
}
#include<vector>
const int N=60,inf=12345678;
int T,n,ans,a[N][N],b[N][N],fa[N],fb[N],w[N],d[N],q[N],l,r;
std::vector<int> e[N];
void dfs(int u)
{
	fr(v,1,n) if(a[u][v]&&v!=fa[u])
	{
		w[v]=w[u]&&b[u][v]; fa[v]=u; dfs(v);
	}
}
void Dfs(int u)
{
	fr(v,1,n) if(b[u][v]&&v!=fb[u]){ fb[v]=u; Dfs(v); }
}
int solve(int u)
{
	fr(i,1,n)
	{
		e[i].clear(); fa[i]=fb[i]=0; w[i]=d[i]=0;
	}
	w[u]=1; dfs(u); Dfs(u);
	int ans=0;
	fr(i,1,n) ans+=!w[i];
	fr(i,1,n) if(i!=u&&!w[fa[i]]){ e[i].push_back(fa[i]); d[fa[i]]++; }
	fr(i,1,n) if(i!=u&&!w[fb[i]]){ e[fb[i]].push_back(i); d[i]++; }
	l=1; r=0;
	fr(i,1,n) if(!w[i]&&d[i]==0) q[++r]=i;
	while(l<=r)
	{
		int i=q[l++];
		fr(j,0,e[i].size()-1)
		{
			d[e[i][j]]--;
			if(!d[e[i][j]]) q[++r]=e[i][j];
		}
	}
	return ans==r?ans:inf;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();
		fr(i,1,n) fr(j,1,n) a[i][j]=b[i][j]=0;
		fr(i,1,n-1)
		{
			int u=read(),v=read();
			a[u][v]=a[v][u]=1;
		}
		fr(i,1,n-1)
		{
			int u=read(),v=read();
			b[u][v]=b[v][u]=1;
		}
		ans=inf;
		fr(i,1,n) ans=std::min(ans,solve(i));
		fr(i,1,n)
		{
			int d=0;
			fr(j,1,n) d+=a[i][j];
			if(d!=1) continue;
			fr(j,1,n) if(a[i][j])
				fr(k,1,n) if(k!=i&&k!=j)
				{
					a[i][j]=a[j][i]=0; a[i][k]=a[k][i]=1;
					ans=std::min(ans,solve(i)+1);
					a[i][j]=a[j][i]=1; a[i][k]=a[k][i]=0;
				}
		}
		printf("%d\n",ans==inf?-1:ans);
	}
	return 0;
}
### Prompt

Your challenge is to write a CPP solution to the following 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

### Response

```cpp
/****************************************************************
*	Author: huhao
*	Email: 826538400@qq.com
*	Create time: 2020-03-20 08:32:35
****************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
	int r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=(r<<3)+(r<<1)+(c^48);
		c=getchar();
	}
	return r*t;
}
#include<vector>
const int N=60,inf=12345678;
int T,n,ans,a[N][N],b[N][N],fa[N],fb[N],w[N],d[N],q[N],l,r;
std::vector<int> e[N];
void dfs(int u)
{
	fr(v,1,n) if(a[u][v]&&v!=fa[u])
	{
		w[v]=w[u]&&b[u][v]; fa[v]=u; dfs(v);
	}
}
void Dfs(int u)
{
	fr(v,1,n) if(b[u][v]&&v!=fb[u]){ fb[v]=u; Dfs(v); }
}
int solve(int u)
{
	fr(i,1,n)
	{
		e[i].clear(); fa[i]=fb[i]=0; w[i]=d[i]=0;
	}
	w[u]=1; dfs(u); Dfs(u);
	int ans=0;
	fr(i,1,n) ans+=!w[i];
	fr(i,1,n) if(i!=u&&!w[fa[i]]){ e[i].push_back(fa[i]); d[fa[i]]++; }
	fr(i,1,n) if(i!=u&&!w[fb[i]]){ e[fb[i]].push_back(i); d[i]++; }
	l=1; r=0;
	fr(i,1,n) if(!w[i]&&d[i]==0) q[++r]=i;
	while(l<=r)
	{
		int i=q[l++];
		fr(j,0,e[i].size()-1)
		{
			d[e[i][j]]--;
			if(!d[e[i][j]]) q[++r]=e[i][j];
		}
	}
	return ans==r?ans:inf;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();
		fr(i,1,n) fr(j,1,n) a[i][j]=b[i][j]=0;
		fr(i,1,n-1)
		{
			int u=read(),v=read();
			a[u][v]=a[v][u]=1;
		}
		fr(i,1,n-1)
		{
			int u=read(),v=read();
			b[u][v]=b[v][u]=1;
		}
		ans=inf;
		fr(i,1,n) ans=std::min(ans,solve(i));
		fr(i,1,n)
		{
			int d=0;
			fr(j,1,n) d+=a[i][j];
			if(d!=1) continue;
			fr(j,1,n) if(a[i][j])
				fr(k,1,n) if(k!=i&&k!=j)
				{
					a[i][j]=a[j][i]=0; a[i][k]=a[k][i]=1;
					ans=std::min(ans,solve(i)+1);
					a[i][j]=a[j][i]=1; a[i][k]=a[k][i]=0;
				}
		}
		printf("%d\n",ans==inf?-1:ans);
	}
	return 0;
}
```