#include<bits/stdc++.h>
using namespace std;
const int N=105;
vector<int>b[N],c[N];
int n,T,now,d[N],vi[N],f1[N],f2[N],v[N],nex[N],head[N];
void addedges(int x,int y){
	nex[++now]=head[x],++d[y];
	head[x]=now,v[now]=y;
}
void get1(int x){
	int si=b[x].size();
	for(int i=0;i<si;i++){
		int v=b[x][i];
		if(v!=f1[x])	f1[v]=x,get1(v);
	}
}
void get2(int x){
	int si=c[x].size();
	for(int i=0;i<si;i++){
		int v=c[x][i];
		if(v!=f2[x])	f2[v]=x,get2(v);
	}
}
queue<int>que;
int check(int rt){
	int cnt=0,res=0;
	f1[rt]=0,get1(rt);
	f2[rt]=0,get2(rt);
	for(int i=1;i<=n;i++)	d[i]=head[i]=0;
	for(int i=1;i<=n;i++)
		if(f1[i]==f2[i])	vi[i]=1;
		else	++cnt,++res,vi[i]=0;
	now=0;
	for(int i=1;i<=n;i++){
		addedges(i,f1[i]);
		if(!vi[f2[i]])	addedges(f2[i],i);
	}
	for(int i=1;i<=n;i++)
		if(!d[i]&&!vi[i])	que.push(i);
	while(!que.empty()){
		int x=que.front();
		que.pop();	--cnt;
		for(int j=head[x];j;j=nex[j])
			if(!vi[v[j]]&&!(--d[v[j]]))
				que.push(v[j]);
	}
	if(cnt)	return -1;
	else	return res;
}
void erase(int x,int y){
	for(vector<int>::iterator i=b[x].begin();i!=b[x].end();i++)
		if(*i==y){
			b[x].erase(i);
			return ;
		}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)	b[i].clear(),c[i].clear();
		for(int i=1,x,y;i<n;i++){
			scanf("%d%d",&x,&y);
			b[x].push_back(y);
			b[y].push_back(x);
		}
		for(int i=1,x,y;i<n;i++){
			scanf("%d%d",&x,&y);
			c[x].push_back(y);
			c[y].push_back(x);
		}
		int ans=INT_MAX;
		for(int i=1;i<=n;i++){
			for(int j=1,k;j<=n;j++){
				if(b[j].size()>1||i==j)	continue;
				k=b[j][0],b[j].clear();
				b[j].push_back(i),erase(k,j);

				int d=check(j);
				if(d!=-1)	ans=min(ans,d+1);
				b[j].clear(),b[j].push_back(k),b[k].push_back(j);
			}
			int d=check(i);
			if(d!=-1)	ans=min(ans,d);
		}
		if(ans==INT_MAX)	puts("-1");
		else	printf("%d\n",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
#include<bits/stdc++.h>
using namespace std;
const int N=105;
vector<int>b[N],c[N];
int n,T,now,d[N],vi[N],f1[N],f2[N],v[N],nex[N],head[N];
void addedges(int x,int y){
	nex[++now]=head[x],++d[y];
	head[x]=now,v[now]=y;
}
void get1(int x){
	int si=b[x].size();
	for(int i=0;i<si;i++){
		int v=b[x][i];
		if(v!=f1[x])	f1[v]=x,get1(v);
	}
}
void get2(int x){
	int si=c[x].size();
	for(int i=0;i<si;i++){
		int v=c[x][i];
		if(v!=f2[x])	f2[v]=x,get2(v);
	}
}
queue<int>que;
int check(int rt){
	int cnt=0,res=0;
	f1[rt]=0,get1(rt);
	f2[rt]=0,get2(rt);
	for(int i=1;i<=n;i++)	d[i]=head[i]=0;
	for(int i=1;i<=n;i++)
		if(f1[i]==f2[i])	vi[i]=1;
		else	++cnt,++res,vi[i]=0;
	now=0;
	for(int i=1;i<=n;i++){
		addedges(i,f1[i]);
		if(!vi[f2[i]])	addedges(f2[i],i);
	}
	for(int i=1;i<=n;i++)
		if(!d[i]&&!vi[i])	que.push(i);
	while(!que.empty()){
		int x=que.front();
		que.pop();	--cnt;
		for(int j=head[x];j;j=nex[j])
			if(!vi[v[j]]&&!(--d[v[j]]))
				que.push(v[j]);
	}
	if(cnt)	return -1;
	else	return res;
}
void erase(int x,int y){
	for(vector<int>::iterator i=b[x].begin();i!=b[x].end();i++)
		if(*i==y){
			b[x].erase(i);
			return ;
		}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)	b[i].clear(),c[i].clear();
		for(int i=1,x,y;i<n;i++){
			scanf("%d%d",&x,&y);
			b[x].push_back(y);
			b[y].push_back(x);
		}
		for(int i=1,x,y;i<n;i++){
			scanf("%d%d",&x,&y);
			c[x].push_back(y);
			c[y].push_back(x);
		}
		int ans=INT_MAX;
		for(int i=1;i<=n;i++){
			for(int j=1,k;j<=n;j++){
				if(b[j].size()>1||i==j)	continue;
				k=b[j][0],b[j].clear();
				b[j].push_back(i),erase(k,j);

				int d=check(j);
				if(d!=-1)	ans=min(ans,d+1);
				b[j].clear(),b[j].push_back(k),b[k].push_back(j);
			}
			int d=check(i);
			if(d!=-1)	ans=min(ans,d);
		}
		if(ans==INT_MAX)	puts("-1");
		else	printf("%d\n",ans);
	}
	return 0;
}

```