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>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=52;

vector<int>ea[maxn],eb[maxn];

int n;

inline void init()
{
	n=read();
	REP(i,1,n)ea[i].clear(),eb[i].clear();
	REP(i,1,n-1)
	{
		int u=read(),v=read();
		ea[u].push_back(v);
		ea[v].push_back(u);
	}
	REP(i,1,n-1)
	{
		int u=read(),v=read();
		eb[u].push_back(v);
		eb[v].push_back(u);
	}
}

int ans;
int fa[maxn],goal[maxn],rq[maxn];
int fake,RQ;

void dfsa(int u,int ff)
{
	for(int v:ea[u])
	{
		if(v==ff)continue;
		dfsa(v,u);
		fa[v]=u;
	}
}

void dfsb(int u,int ff)
{
	for(int v:eb[u])
	{
		if(v==ff)continue;
		goal[v]=u;
		if(goal[v]==fa[v])
		{
			if(rq[u])rq[v]=1,RQ++;
		}
		dfsb(v,u);
	}
}

inline void work(int rt)
{
	memset(fa,0,sizeof(int)*(n+1));
	memset(goal,0,sizeof(int)*(n+1));
	memset(rq,0,sizeof(int)*(n+1)); rq[rt]=1; RQ=1;
	dfsa(rt,0);
	dfsb(rt,0);
	static int rd[maxn];
	static vector<int>ed[maxn];
	
	int sum=0;
	queue<int>q;
	REP(i,1,n)rd[i]=0,ed[i].clear();
	REP(i,1,n)if(!rq[i] && !rq[fa[i]])ed[i].push_back(fa[i]),rd[fa[i]]++;
	REP(i,1,n)if(!rq[i] && !rq[goal[i]])ed[goal[i]].push_back(i),rd[i]++;
	REP(i,1,n)if(!rq[i] && !rd[i])q.push(i);
	
	while(!q.empty())
	{
		int u=q.front();q.pop();sum++;
		for(int v:ed[u])if(!(--rd[v]))q.push(v);
	}
	if(sum==n-RQ)chkmin(ans,n-RQ);
}

inline void work1(int rt,int cg)
{
	memset(fa,0,sizeof(int)*(n+1));
	memset(goal,0,sizeof(int)*(n+1));
	memset(rq,0,sizeof(int)*(n+1)); rq[rt]=1; RQ=1;
	dfsa(rt,0);
	dfsb(rt,0);
	static int rd[maxn];
	static vector<int>ed[maxn];
	int sum=0;
	queue<int>q;
	REP(i,1,n)rd[i]=0,ed[i].clear();
	REP(i,1,n)if(!rq[i] && !rq[fa[i]])ed[i].push_back(fa[i]),rd[fa[i]]++;
	REP(i,1,n)if(!rq[i] && !rq[goal[i]])ed[goal[i]].push_back(i),rd[i]++;
	REP(i,1,n)if(!rq[i] && !rd[i])q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();sum++;
		for(int v:ed[u])if(!(--rd[v]))q.push(v);
	}
	if(sum==n-RQ)chkmin(ans,n-RQ+1);
}

inline void doing()
{
	ans=n+1;
	REP(i,1,n)work(i);

	REP(i,1,n)if(SZ(ea[i])==1)
		REP(j,1,n)if(j!=ea[i].front())
		{
			int rem=ea[i].front();
			ea[i][0]=j;
			ea[rem].erase(find(ea[rem].begin(),ea[rem].end(),i));
			ea[j].push_back(i);
			work1(i,j);
			ea[j].pop_back();
			ea[rem].push_back(i);
			ea[i][0]=rem;
		}
	if(ans==n+1)puts("-1");
	else printf("%d\n",ans);
}

int main()
{
	int t=read();
	while(t--)
	{
		init();
		doing();
	}
	return 0;
}