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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN= +117;
const int MM= +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
struct edge{
	int x,y;
	
};
bool operator <(const edge &a, const edge &b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool operator ==(const edge &a, const edge &b){
	return a.x==b.x&&a.y==b.y;
}
edge ae[NN]={},be[NN]={};
edge com[NN]={};
vector<int> a[NN]={};
int dega[NN]={};
int adj[NN]={};
vector<int> b[NN]={};
vector<int> sam[NN]={};
vector<int> p[NN]={};
bool vis[NN]={};
int tu[NN]={};
bool cir;
void dfs(int x,int fa){
	vis[x]=1;
	for(int i=0;i<sam[x].size();++i){
		int cur=sam[x][i];
		if(cur!=fa){
			dfs(cur,x);
		}
	}
}
void adda(int x,int fa){
	for(int i=0;i<a[x].size();++i){
		int cur=a[x][i];
		if(cur!=fa){
			p[cur].push_back(x);
			adda(cur,x);
		}
	}
}
void addb(int x,int fa){
	for(int i=0;i<b[x].size();++i){
		int cur=b[x][i];
		if(cur!=fa){
			p[x].push_back(cur);
			addb(cur,x);
		}
	}
}
void chk(int x){
	tu[x]=1;
	for(int i=0;i<p[x].size();++i){
		int cur=p[x][i];
		if(tu[cur]==1)cir=1;
		if(!tu[cur])chk(cur);
	}
	tu[x]=2;
}
int calc(int rt){
	for(int i=1;i<=n;++i){
		p[i].clear();
		vis[i]=0;
		tu[i]=0;
	}
	dfs(rt,0);
	int res=n;
	for(int i=1;i<=n;++i){
		if(vis[i]){
			--res;
			for(int j=0;j<a[i].size();++j){
				int cur=a[i][j];
				if(!vis[cur]){
					adda(cur,i);
				}
			}
			for(int j=0;j<b[i].size();++j){
				int cur=b[i][j];
				if(!vis[cur]){
					addb(cur,i);
				}
			}
		}
	}
	cir=0;
	for(int i=1;i<=n;++i){
		if(!tu[i])chk(i);
	}
	if(cir)res=n+1;
	//cerr<<res<<endl;
	return res;
}
void solve(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i].clear();
		b[i].clear();
		sam[i].clear();
		dega[i]=0;
	}
	for(int i=1;i<n;++i){
		int x=read();
		int y=read();
		if(x>y)swap(x,y);
		ae[i].x=x,ae[i].y=y;
		dega[x]++;
		adj[x]=y;
		dega[y]++;
		adj[y]=x;
	}
	for(int i=1;i<n;++i){
		int x=read();
		int y=read();
		if(x>y)swap(x,y);
		be[i].x=x,be[i].y=y;
	}
	sort(ae+1,ae+n);
	sort(be+1,be+n);
	int pa=1,pb=1;
	int ccnt=0;
	while(pa!=n&&pb!=n){
		if(ae[pa]<be[pb])++pa;
		else if(be[pb]<ae[pa])++pb;
		else{
			com[++ccnt]=ae[pa];
			++pa,++pb;
		}
	}
	for(int i=1;i<n;++i){
		int x=ae[i].x,y=ae[i].y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<n;++i){
		int x=be[i].x,y=be[i].y;
		b[x].push_back(y);
		b[y].push_back(x);
	}
	for(int i=1;i<=ccnt;++i){
		int x=com[i].x,y=com[i].y;
		sam[x].push_back(y);
		sam[y].push_back(x);
	}
	int ans=n+1;
	for(int i=1;i<=n;++i){
		ans=min(ans,calc(i));
	}
	for(int i=1;i<=n;++i){
		if(dega[i]==1){
			for(int j=1;j<=n;++j){
				if(i!=j){
					for(int k=1;k<=n;++k){
						a[k].clear();
						sam[k].clear();
					}
					edge now,ad;
					now.x=i,now.y=adj[i];
					ad.x=i,ad.y=j;
					if(now.x>now.y)swap(now.x,now.y);
					if(ad.x>ad.y)swap(ad.x,ad.y);
					for(int i=1;i<n;++i){
						if(ae[i]==now){
							continue;
						}
						int x=ae[i].x,y=ae[i].y;
						a[x].push_back(y);
						a[y].push_back(x);
						if(be[i]==ad){
							x=be[i].x,y=be[i].y;
							sam[x].push_back(y);
							sam[y].push_back(x);
						}
					}
					a[ad.x].push_back(ad.y);
					a[ad.y].push_back(ad.x);
					for(int i=1;i<=ccnt;++i){
						if(com[i]==now)continue;
						int x=com[i].x,y=com[i].y;
						sam[x].push_back(y);
						sam[y].push_back(x);
					}
					ans=min(ans,calc(i)+1);
				}
			}
		}
	}
	if(ans>n){
		printf("-1\n");
	}
	else printf("%d\n",ans);
}
int main(){
	//open();
	int T=read();
	while(T--){
		solve();
	}


	close();
	return 0;
}