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<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#include<iostream>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define VI vector<int>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=55;
struct Graph
{
	vector<int> nxt[MAXN];
	void ins(int x,int y){nxt[x].emplace_back(y);}
	void addedge(int x,int y){ins(x,y);ins(y,x);}
	void clr(){for(int i=1;i<MAXN;i++)nxt[i].clear();}
}G[2],T;
int fa[2][MAXN];
map<int,int> mp[MAXN];
int n,RT;
void init(Graph &a,int x,int o)
{
	for(auto y:a.nxt[x])if(y^fa[o][x])
		fa[o][y]=x,init(a,y,o);
}
bool flag[MAXN];
int du[MAXN],vis[MAXN];
bool isleaf[MAXN],nochange[MAXN];
void init_graph1(Graph &a,int x)
{
	if(fa[1][x])nochange[x]=nochange[fa[1][x]];
	if(fa[0][x]!=fa[1][x])nochange[x]=0;
	for(auto y:a.nxt[x])if(y^fa[1][x])
		init_graph1(a,y); 
}
void init_graph(Graph &a,int x)
{
	if(fa[1][x])flag[x]=flag[fa[1][x]];
	if(fa[0][x]!=fa[1][x])flag[x]=0;
	if(!flag[x]&&fa[0][x]==fa[1][x]){flag[0]=1;}
	if(fa[0][x]!=fa[1][x])
	{
		if(!nochange[fa[0][x]])T.ins(x,fa[0][x]),++du[fa[0][x]];
		if(!nochange[fa[1][x]])T.ins(fa[1][x],x),++du[x];
	}
	for(auto y:a.nxt[x])if(y^fa[1][x])
		init_graph(a,y);
}
queue<int> li; 
int query(int rt)
{
	fa[0][rt]=fa[1][rt]=0;RT=rt;
	init(G[0],rt,0);init(G[1],rt,1);T.clr();memset(du,0,sizeof(du));
//	puts("YES");
	flag[rt]=1;flag[0]=0;nochange[rt]=1;
	init_graph1(G[1],rt);
	init_graph(G[1],rt);
	if(flag[0])return 1e9;
	int ret=0;
	for(int i=1;i<=n;i++)if(fa[0][i]!=fa[1][i]&&i!=rt)++ret;
	int sz=0;
	for(int i=1;i<=n;i++)if(!du[i])li.push(i);
	while(!li.empty())
	{
		int x=li.front();li.pop();++sz;
		for(auto y:T.nxt[x])if(!(--du[y]))li.push(y);
	}
	if(sz!=n)return 1e9;
	return ret;
}
struct edge{int x,y;}E[MAXN];
void solve()
{
	G[0].clr();G[1].clr();
	n=read();
	for(int i=1;i<MAXN;i++)mp[i].clear();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		G[0].addedge(x,y);
	}int rt=-1;
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();E[i].x=x;E[i].y=y;
		G[1].addedge(x,y);
	}int ans=1e9;
//	chkmin(ans,query(3));
	for(int i=1;i<=n;i++)
		chkmin(ans,query(i));
	memset(du,0,sizeof(du));memset(isleaf,0,sizeof(isleaf));
	for(int i=1;i<n;i++)++du[E[i].x],++du[E[i].y];
	for(int i=1;i<=n;i++)if(du[i]==1)isleaf[i]=1;
	for(int i=1;i<=n;i++)if(isleaf[i])
	{
		for(int j=1;j<=n;j++)if(i!=j)
		{
			G[1].clr();
			for(int k=1;k<n;k++)if(E[k].x!=i&&E[k].y!=i)
				G[1].addedge(E[k].x,E[k].y);
			G[1].addedge(i,j);
			chkmin(ans,query(i)+1);
		}
	}
//	}
	if(ans==1e9)pr2(-1);
	else pr2(ans);
}
int main()
{
//	freopen("b.in","r",stdin);
	
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	#ifdef Rose
		double BeginJudgeTime=clock();
	#endif
	for(int __=read();__;--__)solve();
	#ifdef Rose
		double EndJudgeTime=clock();
		cerr<<"JudgeTime is"<<" ";
		cerr<<(EndJudgeTime-BeginJudgeTime)/CLOCKS_PER_SEC<<endl;
	#endif
	return 0;
}