#include <bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define for1(a,b,i) for(int i=a;i<=b;++i)
#define FOR2(a,b,i) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
inline int read() {
    int f=1,sum=0;
    char x=getchar();
    for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;
    for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';
    return f*sum;
}

#define M 55
int n;
int du[M];
bool vis[M],re[M];
int e_size,head[M],fa[M],pre[M];
struct node {
	int x,y;
	
	inline void in() {
		x=read(),y=read();
		if(x>y) swap(x,y);
	}
	inline bool operator <(const node &a) const {
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
}a[M],b[M];

struct edge {int v,nxt;}e[M*2];

inline void e_add(int u,int v) {
	e[++e_size]=(edge){v,head[u]};
	head[u]=e_size;
}

inline bool check() {
	for1(1,n-1,i) if(a[i].x!=b[i].x||a[i].y!=b[i].y) return 0;
	return 1;
}

inline void dfs1(int x,int *ha) {
	for(int i=head[x];i;i=e[i].nxt) {
		int v=e[i].v;
		if(v==ha[x]) continue;
		ha[v]=x,dfs1(v,ha);
	}
}

inline void dfs2(int x) {
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt) {
		int v=e[i].v;
		if(v==pre[x]||fa[v]!=x) continue;
		dfs2(v);
	}
}

inline int calc_(int x,int y) {
	e_size=0;
	memset(re,0,sizeof(re));
	memset(du,0,sizeof(du));
	memset(vis,0,sizeof(vis));
	memset(pre,0,sizeof(pre));
	memset(head,0,sizeof(head));
	re[x]=1;
	++du[x],++du[y];
	e_add(x,y),e_add(y,x);
	for1(1,n-1,i) {
		int u=a[i].x;
		int v=a[i].y;
		if(u==x||v==x) continue;
		++du[u],++du[v];
		e_add(u,v),e_add(v,u);
	}
	dfs1(x,pre),dfs2(x);
	//for1(1,n,i) cout<<pre[i]<<" "; cout<<endl;
	int cnt=0,now=0;
	for1(1,n,i) now+=vis[i];
	cnt=now;
	while (now!=n) {
		int pos=0;
		for1(1,n,i) if(!vis[i]&&vis[fa[i]]&&!re[i]&&du[i]==1) {pos=i;break;}
		if(!pos) break;
		//cout<<pos<<" "<<pre[pos]<<endl;
		re[pos]=vis[pos]=1,++now;
		--du[pre[pos]],++du[fa[pos]];
	}
	return now==n?n-cnt+1:1e9;
}

int main () {
//	freopen("a.in","r",stdin);
	int Test_=read();
	while (Test_--) {
		n=read();
		for1(1,n-1,i) a[i].in();
		for1(1,n-1,i) b[i].in();
		sort(a+1,a+n),sort(b+1,b+n);
		
		if(check()) puts("0");
		else {
			int shu[M]={0};
			for1(1,n-1,i) ++shu[a[i].x],++shu[a[i].y];
			int ans=1e9;
			for1(1,n,i) if(shu[i]==1) {
				e_size=0;
				memset(fa,0,sizeof(fa));
				memset(head,0,sizeof(head));
				for1(1,n-1,j) e_add(b[j].x,b[j].y),e_add(b[j].y,b[j].x);
				dfs1(i,fa);
				for1(1,n,j) if(i!=j) {
					int num=calc_(i,j);
					ans=min(ans,num);
				}
			}
			if(ans==1e9) ans=-1;
			printf("%d\n",ans);
		}
	}
}
### Prompt

Please formulate 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>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define for1(a,b,i) for(int i=a;i<=b;++i)
#define FOR2(a,b,i) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
inline int read() {
    int f=1,sum=0;
    char x=getchar();
    for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;
    for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';
    return f*sum;
}

#define M 55
int n;
int du[M];
bool vis[M],re[M];
int e_size,head[M],fa[M],pre[M];
struct node {
	int x,y;
	
	inline void in() {
		x=read(),y=read();
		if(x>y) swap(x,y);
	}
	inline bool operator <(const node &a) const {
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
}a[M],b[M];

struct edge {int v,nxt;}e[M*2];

inline void e_add(int u,int v) {
	e[++e_size]=(edge){v,head[u]};
	head[u]=e_size;
}

inline bool check() {
	for1(1,n-1,i) if(a[i].x!=b[i].x||a[i].y!=b[i].y) return 0;
	return 1;
}

inline void dfs1(int x,int *ha) {
	for(int i=head[x];i;i=e[i].nxt) {
		int v=e[i].v;
		if(v==ha[x]) continue;
		ha[v]=x,dfs1(v,ha);
	}
}

inline void dfs2(int x) {
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt) {
		int v=e[i].v;
		if(v==pre[x]||fa[v]!=x) continue;
		dfs2(v);
	}
}

inline int calc_(int x,int y) {
	e_size=0;
	memset(re,0,sizeof(re));
	memset(du,0,sizeof(du));
	memset(vis,0,sizeof(vis));
	memset(pre,0,sizeof(pre));
	memset(head,0,sizeof(head));
	re[x]=1;
	++du[x],++du[y];
	e_add(x,y),e_add(y,x);
	for1(1,n-1,i) {
		int u=a[i].x;
		int v=a[i].y;
		if(u==x||v==x) continue;
		++du[u],++du[v];
		e_add(u,v),e_add(v,u);
	}
	dfs1(x,pre),dfs2(x);
	//for1(1,n,i) cout<<pre[i]<<" "; cout<<endl;
	int cnt=0,now=0;
	for1(1,n,i) now+=vis[i];
	cnt=now;
	while (now!=n) {
		int pos=0;
		for1(1,n,i) if(!vis[i]&&vis[fa[i]]&&!re[i]&&du[i]==1) {pos=i;break;}
		if(!pos) break;
		//cout<<pos<<" "<<pre[pos]<<endl;
		re[pos]=vis[pos]=1,++now;
		--du[pre[pos]],++du[fa[pos]];
	}
	return now==n?n-cnt+1:1e9;
}

int main () {
//	freopen("a.in","r",stdin);
	int Test_=read();
	while (Test_--) {
		n=read();
		for1(1,n-1,i) a[i].in();
		for1(1,n-1,i) b[i].in();
		sort(a+1,a+n),sort(b+1,b+n);
		
		if(check()) puts("0");
		else {
			int shu[M]={0};
			for1(1,n-1,i) ++shu[a[i].x],++shu[a[i].y];
			int ans=1e9;
			for1(1,n,i) if(shu[i]==1) {
				e_size=0;
				memset(fa,0,sizeof(fa));
				memset(head,0,sizeof(head));
				for1(1,n-1,j) e_add(b[j].x,b[j].y),e_add(b[j].y,b[j].x);
				dfs1(i,fa);
				for1(1,n,j) if(i!=j) {
					int num=calc_(i,j);
					ans=min(ans,num);
				}
			}
			if(ans==1e9) ans=-1;
			printf("%d\n",ans);
		}
	}
}
```