#include <bits/stdc++.h>
using namespace std;
 
const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-') f=-1; ch=nc(); }
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc(); }
	return i*f;
}
 
const int N=52;
int n;
vector <int> e1[N];
vector <int> e2[N];
vector <int> const_point; 
 
typedef set <int> :: iterator it;
 
struct Tree {
	int fa[N];
	set <int> e[N];
	inline void insert(int x,int y) {e[x].insert(y); fa[y]=x;}
	inline bool count(int u,int v) {return e[u].count(v);}
	inline void erase(int u,int v) {e[u].erase(v);}
	inline bool leaf(int u) {return e[u].empty();}
};
 
inline void dfs1(int x,Tree  &t,int f=0) {
	for(auto v:e1[x]) if(v!=f) {
		t.insert(x,v); dfs1(v,t,x);
	}
}
inline void dfs2(int x,Tree &t,int f=0) {
	for(auto v:e2[x]) if(v!=f) {
		t.insert(x,v); dfs2(v,t,x);
	}
}
 
inline int calc_cost(Tree &a,Tree &b) {
	if(const_point.size()==n) return 0;
	for(auto u:const_point)
		for(auto v:a.e[u])
			if(b.count(u,v)) {
				a.erase(u,v);
				b.erase(u,v);
				const_point.push_back(v);
				return calc_cost(a,b);
			}
	for(auto u:const_point)
		for(auto v:b.e[u]) {
			if(a.leaf(v)) {
				a.erase(a.fa[v],v);
				a.insert(u,v); a.fa[v]=u;
				return calc_cost(a,b)+1;
			}
		}
	return 1e9;
}
 
inline int calc(int rt) {
	Tree a; Tree b;
	const_point.clear();
	const_point.push_back(rt);
	dfs1(rt,a); dfs2(rt,b);
	return calc_cost(a,b);	
}
 
inline void erase_edge(int x,int y) {
	e1[x].erase(lower_bound(e1[x].begin(),e1[x].end(),y));
	e1[y].erase(lower_bound(e1[y].begin(),e1[y].end(),x));
}
inline void add_edge(int x,int y) {
	e1[x].push_back(y); e1[y].push_back(x);
	sort(e1[x].begin(),e1[x].end());
	sort(e1[y].begin(),e1[y].end());
}
int main() {
	for(int T=rd();T;T--) {
		n=rd();
		for(int i=1;i<=n;i++) e1[i].clear(), e2[i].clear();
		for(int i=1;i<n;i++) {
			int x=rd(), y=rd();
			e1[x].push_back(y);
			e1[y].push_back(x);
		}
		for(int i=1;i<n;i++) {
			int x=rd(), y=rd();
			e2[x].push_back(y);
			e2[y].push_back(x);
		}
		int ans=1e9;
		for(int i=1;i<=n;i++) sort(e1[i].begin(),e1[i].end()), sort(e2[i].begin(),e2[i].end());
		for(int i=1;i<=n && ans>1;i++) ans=min(ans,calc(i));
		for(int i=1;i<=n && ans>1;i++) {
			if(e1[i].size()==1) {
				int y=e1[i].front();
				erase_edge(y,i);
				for(int j=1;j<=n;j++)
					if(j!=i && j!=y) {
						add_edge(i,j);
						ans=min(ans,1+calc(i));
						erase_edge(i,j); 
					}
				add_edge(y,i);
			}
		}
		cout<<(ans<1e9 ? ans : -1)<<'\n'; 
	}
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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 RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-') f=-1; ch=nc(); }
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc(); }
	return i*f;
}
 
const int N=52;
int n;
vector <int> e1[N];
vector <int> e2[N];
vector <int> const_point; 
 
typedef set <int> :: iterator it;
 
struct Tree {
	int fa[N];
	set <int> e[N];
	inline void insert(int x,int y) {e[x].insert(y); fa[y]=x;}
	inline bool count(int u,int v) {return e[u].count(v);}
	inline void erase(int u,int v) {e[u].erase(v);}
	inline bool leaf(int u) {return e[u].empty();}
};
 
inline void dfs1(int x,Tree  &t,int f=0) {
	for(auto v:e1[x]) if(v!=f) {
		t.insert(x,v); dfs1(v,t,x);
	}
}
inline void dfs2(int x,Tree &t,int f=0) {
	for(auto v:e2[x]) if(v!=f) {
		t.insert(x,v); dfs2(v,t,x);
	}
}
 
inline int calc_cost(Tree &a,Tree &b) {
	if(const_point.size()==n) return 0;
	for(auto u:const_point)
		for(auto v:a.e[u])
			if(b.count(u,v)) {
				a.erase(u,v);
				b.erase(u,v);
				const_point.push_back(v);
				return calc_cost(a,b);
			}
	for(auto u:const_point)
		for(auto v:b.e[u]) {
			if(a.leaf(v)) {
				a.erase(a.fa[v],v);
				a.insert(u,v); a.fa[v]=u;
				return calc_cost(a,b)+1;
			}
		}
	return 1e9;
}
 
inline int calc(int rt) {
	Tree a; Tree b;
	const_point.clear();
	const_point.push_back(rt);
	dfs1(rt,a); dfs2(rt,b);
	return calc_cost(a,b);	
}
 
inline void erase_edge(int x,int y) {
	e1[x].erase(lower_bound(e1[x].begin(),e1[x].end(),y));
	e1[y].erase(lower_bound(e1[y].begin(),e1[y].end(),x));
}
inline void add_edge(int x,int y) {
	e1[x].push_back(y); e1[y].push_back(x);
	sort(e1[x].begin(),e1[x].end());
	sort(e1[y].begin(),e1[y].end());
}
int main() {
	for(int T=rd();T;T--) {
		n=rd();
		for(int i=1;i<=n;i++) e1[i].clear(), e2[i].clear();
		for(int i=1;i<n;i++) {
			int x=rd(), y=rd();
			e1[x].push_back(y);
			e1[y].push_back(x);
		}
		for(int i=1;i<n;i++) {
			int x=rd(), y=rd();
			e2[x].push_back(y);
			e2[y].push_back(x);
		}
		int ans=1e9;
		for(int i=1;i<=n;i++) sort(e1[i].begin(),e1[i].end()), sort(e2[i].begin(),e2[i].end());
		for(int i=1;i<=n && ans>1;i++) ans=min(ans,calc(i));
		for(int i=1;i<=n && ans>1;i++) {
			if(e1[i].size()==1) {
				int y=e1[i].front();
				erase_edge(y,i);
				for(int j=1;j<=n;j++)
					if(j!=i && j!=y) {
						add_edge(i,j);
						ans=min(ans,1+calc(i));
						erase_edge(i,j); 
					}
				add_edge(y,i);
			}
		}
		cout<<(ans<1e9 ? ans : -1)<<'\n'; 
	}
}
```