p03259 AtCoder Grand Contest 027 - Grafting_33255
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
#include<bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef long double louble;

#define lf ('\n')

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 53 , __ = _<<1;

struct edges
{
	set<int> e[_];
	inline set<int>& operator [] (int x){return e[x];}
	inline void adde(int a,int b){e[a].emplace(b);}
	inline void addde(int a,int b){adde(a,b),adde(b,a);}
	void cls(){for(auto &i:e)i.clear();}
}e1,e2;

int n,du[_];
int fa1[_],fa2[_];
int col1[_],col2[_];

void dfsfa2(int x,int ff){fa2[x]=ff;for(auto b:e2[x])if(b!=ff)dfsfa2(b,x);}

int nowans;

void dfs(int x)
{
	col1[x]=col2[x]=2,nowans--;
	for(auto b2:e2[x])
	{
		if(b2==fa2[x])continue;
		if(e1[x].count(b2))dfs(b2);
		else col2[b2]=1;
	}
}

inline int able()
{
	for(int i=1;i<nowans;i++)
	{
		int x=0;
		for(int j=1;j<=n;j++)if(col1[j]==1 && col2[j]==1){x=j;break;}
		if(!x)return 0;
		col1[x]=col2[x]=2;
		for(auto b:e1[x])if(--du[b]==1 && col1[b]==0)col1[b]=1;
		for(auto b:e2[x])if(b!=fa2[x])col2[b]=1;
	}
	return 1;
}

int duBuf[_];

void finder()
{
	e1.cls(),e2.cls();
	memset(duBuf,0,sizeof(duBuf));
	
	n=ty();
	for(int i=1,a,b;i<n;i++)a=ty(),b=ty(),e1.addde(a,b),duBuf[a]++,duBuf[b]++;
	for(int i=1,a,b;i<n;i++)a=ty(),b=ty(),e2.addde(a,b);
	
	if(n<=2){cout<<0<<lf;return;}

	int ans=1e9;
	for(int i=1;i<=n;i++)
	{
		memset(col1,0,sizeof(col1)),memset(col2,0,sizeof(col2));
		nowans=n,col2[i]=1,dfsfa2(i,0),memcpy(du,duBuf,sizeof(du));
		for(int j=1;j<=n;j++)if(du[j]==1)col1[j]=1;
		if(able()){ans=n;break;}
	}
	for(int i=1;i<=n;i++)
	{
		memset(col1,0,sizeof(col1)),memset(col2,0,sizeof(col2));
		nowans=n,dfsfa2(i,0),dfs(i),memcpy(du,duBuf,sizeof(du));
		for(int j=1;j<=n;j++)if(!col1[j] && du[j]==1)col1[j]=1;
		if(nowans<ans && able())ans=nowans;
	}

	if(ans>n)ans=-1;
	cout<<ans<<lf;
}

int main()
{//
	ios::sync_with_stdio(0),cout.tie(0);
	
	int t=ty();
	while(t--)finder();

	return 0;
}
