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 <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint T;
llint n;
vector<llint> G[55], G2[55];
llint par[55], par2[55];

void dfs(int v, int p, vector<llint> G[], llint par[])
{
	par[v] = p;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		dfs(G[v][i], v, G, par);
	}
}

bool dfs2(int v, int p, bool flag)
{
	if(par[v] == par2[v] && flag) return false;
	
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		if(!dfs2(G[v][i], v, flag || (par[v] != par2[v]))) return false;
	}
	return true;
}

vector<llint> g[55];
vector<int> topo;
bool used[55];

void tpsort(int v)
{
	used[v] = true;
	for(int i = 0; i < g[v].size(); i++){
		if(!used[g[v][i]]) tpsort(g[v][i]);
	}
	topo.push_back(v);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> T;
	for(int t = 0; t < T; t++){
		cin >> n;
		for(int i = 1; i <= n; i++) G[i].clear(), G2[i].clear();
		
		llint u, v;
		for(int i = 0; i < n-1; i++){
			cin >> u >> v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		for(int i = 0; i < n-1; i++){
			cin >> u >> v;
			G2[u].push_back(v);
			G2[v].push_back(u);
		}
		
		llint ans = inf;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				
				llint v;
				if(i != j){
					if(G[i].size() > 1) continue;
					v = G[i][0];
					if(v == j) continue;
					G[i].pop_back();
					G[i].push_back(j);
					G[j].push_back(i);
					for(int k = 0; k < G[v].size(); k++){
						if(G[v][k] == i){
							G[v].erase(G[v].begin()+k);
							break;
						}
					}
				}
				dfs(i, 0, G, par);
				dfs(i, 0, G2, par2);
				
				llint cnt = 0;
				for(int k = 1; k <= n; k++){
					if(par[k] != par2[k]) cnt++;
				}
				
				for(int k = 1; k <= n; k++) g[k].clear();
				for(int k = 1; k <= n; k++){
					if(par[k] == par2[k]) continue;
					if(par[par[k]] != par2[par[k]]) g[k].push_back(par[k]);
					if(par[par2[k]] != par2[par2[k]]) g[par2[k]].push_back(k);
				}
				
				topo.clear();
				for(int k = 1; k <= n; k++) used[k] = false;
				for(int k = 1; k <= n; k++) if(!used[k]) tpsort(k);
				reverse(topo.begin(), topo.end());
				
				bool flag = true;
				for(int k = 1; k <= n; k++) used[k] = false;
				for(int k = 0; k < topo.size(); k++){
					int v = topo[k];
					used[v] = true;
					for(int l = 0; l < g[v].size(); l++){
						if(used[g[v][l]]) flag = false;
					}
				}
				
				flag &= dfs2(i, 0, false);
				
				if(i != j){
					G[j].pop_back();
					G[i].pop_back();
					G[i].push_back(v);
					G[v].push_back(i);
					cnt++;
				}
				
				if(flag) ans = min(ans, cnt);
			}
		}
		
		if(ans > inf/2) ans = -1;
		cout << ans << endl;
	}
	
	return 0;
}