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 <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <queue>
    const int N = 205; 
    typedef long long ll; 
    using namespace std;
     
    int T, n, vis[N], in[N], pa[N], pb[N], da[N], ans, flag; 
    vector<int> g[N], ga[N], gb[N];
    queue<int> q; 
     
    template < typename T >
    inline T read()
    {
    	T x = 0, w = 1; char c = getchar();
    	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    	return x * w; 
    }
     
    void dfs(int u, int fa, vector<int> *g, int *p)
    {
    	p[u] = fa;
    	for(int v, i = 0; i < g[u].size(); i++)
    		if((v = g[u][i]) != fa) dfs(v, u, g, p); 		
    }
     
    int solve()
    {
    	int cnt = 0, tmp = 0; 
    	for(int i = 0; i <= n; i++) vis[i] = in[i] = 0;
    	for(int i = 1; i <= n; i++) if(pa[i] != pb[i]) vis[i] = 1, cnt++; 
    	for(int i = 1; i <= n; i++) if(!vis[i] && vis[pa[i]]) return -1; 
    	for(int i = 1; i <= n; i++) g[i].clear();
    	for(int i = 1; i <= n; i++)
    		if(vis[i])
    		{
    			if(vis[pa[i]]) g[i].push_back(pa[i]), in[pa[i]]++; 
    			if(vis[pb[i]]) g[pb[i]].push_back(i), in[i]++; 
    		}
    	for(int i = 1; i <= n; i++) if(!in[i] && vis[i]) q.push(i); 
    	while(!q.empty())
    	{
    		int u = q.front(); q.pop(); tmp++; 
    		for(int v, i = 0; i < g[u].size(); i++)
    		{
    			v = g[u][i], in[v]--;
    			if(!in[v]) q.push(v); 
    		}
    	}
    	if(cnt != tmp) return -1;
    	else return cnt; 
    }
     
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("cpp.in", "r", stdin); 
    #endif
    	T = read <int> ();
    	while(T--)
    	{
    		n = read <int> ();
    		for(int i = 1; i <= n; i++) ga[i].clear(), gb[i].clear(), da[i] = 0; 
    		for(int u, v, i = 1; i < n; i++)
    		{
    			u = read <int> (), v = read <int> ();
    			ga[u].push_back(v), ga[v].push_back(u), da[u]++, da[v]++; 
    		}
    		for(int u, v, i = 1; i < n; i++)
    		{
    			u = read <int> (), v = read <int> ();
    			gb[u].push_back(v), gb[v].push_back(u); 
    		}
    		dfs(1, 0, ga, pa), dfs(1, 0, gb, pb);
    		ans = n + 1, flag = 1;
    		for(int i = 1; i <= n; i++) if(pa[i] != pb[i]) flag = 0;
    		if(flag) { puts("0"); continue; }
    		for(int tmp, i = 1; i <= n; i++)
    			if(da[i] == 1)
    			{
    				dfs(i, 0, gb, pb); 
    				for(int j = 1; j <= n; j++)
    					if(j != i)
    					{
    						dfs(j, 0, ga, pa), pa[i] = 0, pa[j] = i; 
    						tmp = solve(); 
    						if(tmp != -1) ans = min(ans, tmp + 1); 
    					}
    			}
    		printf("%d\n", ans == n + 1 ? -1 : ans); 
    	}
    	return 0;
    }