#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int t;
vector<int>edge[55],edge2[55];
int n;
int up[55],up2[55];
int beg[55],en[55],beg2[55],en2[55],nxt,nxt2;
void dfs(int v,int u){
	up[v] = u; beg[v] = nxt++;
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		dfs(edge[v][i],v);
	}
	en[v] = nxt-1;
}
void dfs2(int v,int u){
	up2[v] = u; beg2[v] = nxt2++;
	for(int i=0;i<edge2[v].size();i++){
		if(edge2[v][i] == u) continue;
		dfs2(edge2[v][i],v);
	}
	en2[v] = nxt2-1;
}

bool need[55];
bool used[55];
void go(int v,int u){
	used[v] = 1;
	for(int i=0;i<edge[v].size();i++){
	    if(edge[v][i] == u) continue;
		int d = POSL(edge2[v],edge[v][i]);
		if(d == edge2[v].size() || edge2[v][d] != edge[v][i]) continue;
		go(edge[v][i],v);
	}
}
vector<int>edge_tp[55];
void _dfs(int v,int u){
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		if(!used[v] && !used[edge[v][i]]){
			edge_tp[v].pb(edge[v][i]);
		}
		_dfs(edge[v][i],v);
	}
}
void _dfs2(int v,int u){
	for(int i=0;i<edge2[v].size();i++){
		if(edge2[v][i] == u) continue;
		if(!used[v] && !used[edge2[v][i]]){
			edge_tp[edge2[v][i]].pb(v);
		}
		_dfs2(edge2[v][i],v);
	}
}
bool find_cycle(){
	int in[55]={};
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge_tp[i].size();j++){
			in[edge_tp[i][j]]++;
		}
	}
	queue<int>que;
	for(int i=1;i<=n;i++){
		if(!in[i]) que.push(i);
	}
	while(!que.empty()){
		int q = que.front(); que.pop();
		for(int i=0;i<edge_tp[q].size();i++){
			in[edge_tp[q][i]]--;
			if(in[edge_tp[q][i]] == 0){
				que.push(edge_tp[q][i]);
			}
		}
	}
	for(int i=1;i<=n;i++) if(in[i]) return true;
	return false;
}
int sol2(int v){
	nxt = 0; nxt2 = 0;
	for(int i=1;i<=n;i++){
		SORT(edge[i]);
		SORT(edge2[i]);
	}
	dfs(v,-1);
	dfs2(v,-1);
	for(int i=1;i<=n;i++){
		used[i] = 0;
	}
	go(v,-1);
	for(int i=1;i<=n;i++){
		edge_tp[i].clear();
	}
	_dfs(v,-1);
	_dfs2(v,-1);
	if(find_cycle()) return INF;
	int ret = 0;
	for(int i=1;i<=n;i++){
		ret += (!used[i]);
	}
	return ret;
}
void sol(){
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b; cin>>a>>b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	for(int i=0;i<n-1;i++){
		int a,b; cin>>a>>b;
		edge2[a].pb(b);
		edge2[b].pb(a);
	}
	int ans = INF;
	for(int v=1;v<=n;v++){
		if(edge[v].size() > 1) continue;
		ans = min(ans,sol2(v));
		if(ans <= 1) continue;
		int to = edge[v][0];
		for(int u=1;u<=n;u++){
			if(v == u) continue;
			if(to == u) continue;
			edge[v].clear();
			for(int j=0;j<edge[to].size();j++){
				if(edge[to][j] == v){
					swap(edge[to][j],edge[to][edge[to].size()-1]);
					edge[to].pop_back();
					break;
				}
			}
			edge[v].pb(u);
			edge[u].pb(v);
			ans = min(ans,sol2(v)+1);
			
			edge[v].clear();
			for(int j=0;j<edge[u].size();j++){
				if(edge[u][j] == v){
					swap(edge[u][j],edge[u][edge[u].size()-1]);
					edge[u].pop_back();
					break;
				}
			}
			edge[v].pb(to);
			edge[to].pb(v);
		}
	}
	if(ans > 1e7) ans = -1;
	cout << ans << endl;
}
int main(){
	cin>>t;
	rep(i,t){
		rep(j,55) edge[j].clear();
		rep(j,55) edge2[j].clear();
		sol();
	}
}
### Prompt

In cpp, your task is to solve 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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int t;
vector<int>edge[55],edge2[55];
int n;
int up[55],up2[55];
int beg[55],en[55],beg2[55],en2[55],nxt,nxt2;
void dfs(int v,int u){
	up[v] = u; beg[v] = nxt++;
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		dfs(edge[v][i],v);
	}
	en[v] = nxt-1;
}
void dfs2(int v,int u){
	up2[v] = u; beg2[v] = nxt2++;
	for(int i=0;i<edge2[v].size();i++){
		if(edge2[v][i] == u) continue;
		dfs2(edge2[v][i],v);
	}
	en2[v] = nxt2-1;
}

bool need[55];
bool used[55];
void go(int v,int u){
	used[v] = 1;
	for(int i=0;i<edge[v].size();i++){
	    if(edge[v][i] == u) continue;
		int d = POSL(edge2[v],edge[v][i]);
		if(d == edge2[v].size() || edge2[v][d] != edge[v][i]) continue;
		go(edge[v][i],v);
	}
}
vector<int>edge_tp[55];
void _dfs(int v,int u){
	for(int i=0;i<edge[v].size();i++){
		if(edge[v][i] == u) continue;
		if(!used[v] && !used[edge[v][i]]){
			edge_tp[v].pb(edge[v][i]);
		}
		_dfs(edge[v][i],v);
	}
}
void _dfs2(int v,int u){
	for(int i=0;i<edge2[v].size();i++){
		if(edge2[v][i] == u) continue;
		if(!used[v] && !used[edge2[v][i]]){
			edge_tp[edge2[v][i]].pb(v);
		}
		_dfs2(edge2[v][i],v);
	}
}
bool find_cycle(){
	int in[55]={};
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge_tp[i].size();j++){
			in[edge_tp[i][j]]++;
		}
	}
	queue<int>que;
	for(int i=1;i<=n;i++){
		if(!in[i]) que.push(i);
	}
	while(!que.empty()){
		int q = que.front(); que.pop();
		for(int i=0;i<edge_tp[q].size();i++){
			in[edge_tp[q][i]]--;
			if(in[edge_tp[q][i]] == 0){
				que.push(edge_tp[q][i]);
			}
		}
	}
	for(int i=1;i<=n;i++) if(in[i]) return true;
	return false;
}
int sol2(int v){
	nxt = 0; nxt2 = 0;
	for(int i=1;i<=n;i++){
		SORT(edge[i]);
		SORT(edge2[i]);
	}
	dfs(v,-1);
	dfs2(v,-1);
	for(int i=1;i<=n;i++){
		used[i] = 0;
	}
	go(v,-1);
	for(int i=1;i<=n;i++){
		edge_tp[i].clear();
	}
	_dfs(v,-1);
	_dfs2(v,-1);
	if(find_cycle()) return INF;
	int ret = 0;
	for(int i=1;i<=n;i++){
		ret += (!used[i]);
	}
	return ret;
}
void sol(){
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b; cin>>a>>b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	for(int i=0;i<n-1;i++){
		int a,b; cin>>a>>b;
		edge2[a].pb(b);
		edge2[b].pb(a);
	}
	int ans = INF;
	for(int v=1;v<=n;v++){
		if(edge[v].size() > 1) continue;
		ans = min(ans,sol2(v));
		if(ans <= 1) continue;
		int to = edge[v][0];
		for(int u=1;u<=n;u++){
			if(v == u) continue;
			if(to == u) continue;
			edge[v].clear();
			for(int j=0;j<edge[to].size();j++){
				if(edge[to][j] == v){
					swap(edge[to][j],edge[to][edge[to].size()-1]);
					edge[to].pop_back();
					break;
				}
			}
			edge[v].pb(u);
			edge[u].pb(v);
			ans = min(ans,sol2(v)+1);
			
			edge[v].clear();
			for(int j=0;j<edge[u].size();j++){
				if(edge[u][j] == v){
					swap(edge[u][j],edge[u][edge[u].size()-1]);
					edge[u].pop_back();
					break;
				}
			}
			edge[v].pb(to);
			edge[to].pb(v);
		}
	}
	if(ans > 1e7) ans = -1;
	cout << ans << endl;
}
int main(){
	cin>>t;
	rep(i,t){
		rep(j,55) edge[j].clear();
		rep(j,55) edge2[j].clear();
		sol();
	}
}
```