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<bits/stdc++.h>
#define maxn 10000
#define INF 2e9
using namespace std;
multiset<int> son[2][maxn];
int need[maxn], n, head[maxn], nxt[maxn], a[maxn], edge, deg[maxn], dl[maxn];
void create(int u, int v)
{
	edge++; a[edge] = v; nxt[edge] = head[u]; head[u] = edge; deg[v]++;
}
void dfs(int u, int fa)
{
	need[u] = 0;
	for (set<int>::iterator it = son[0][u].begin(); it != son[0][u].end(); it++)
	{
		int x = *it;
		if (x != fa && son[1][u].find(x) != son[1][u].end())
			dfs(x, u);
	}
}
void get_fa(int c, int u, int fa)
{
	if (need[u] && need[fa])
	{
		if (c == 0) create(u, fa);
		else create(fa, u);
	}
	for (set<int>::iterator it = son[c][u].begin(); it != son[c][u].end(); it++)
	{
		int x = *it;
		if (x != fa) get_fa(c, x, u);
	}
}
int check(int rt)
{
	for (int i = 1; i <= n; i++)
		need[i] = 1;
	dfs(rt, 0);
	get_fa(0, rt, 0);
	get_fa(1, rt, 0);
	int lef = 1, righ = 0, sum = 0;
	for (int i = 1; i <= n; i++)
		if (need[i])
		{
			sum++;
			if (deg[i] == 0) dl[++righ] = i;
		}
	while (lef <= righ)
	{
		int u = dl[lef];
		for (int i = head[u]; i; i = nxt[i])
		{
			int v = a[i];
			deg[v]--;
			if (deg[v] == 0) dl[++righ] = v;
		}
		lef++;
	}
	edge = 0;
	for (int i = 1; i <= n; i++)
		head[i] = deg[i] = 0;
	if (righ == sum) return sum;
	else return INF;
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n - 1; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			son[0][u].insert(v);
			son[0][v].insert(u);
		}
		for (int i = 1; i <= n - 1; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			son[1][u].insert(v);
			son[1][v].insert(u);
		}
		int res = INF;
		for (int i = 1; i <= n; i++)
			res = min(res, check(i));
		for (int i = 1; i <= n; i++)
			if (son[0][i].size() == 1)
			{
				int x = *son[0][i].begin();
				son[0][i].erase(x);
				son[0][x].erase(i);
				for (int j = 1; j <= n; j++)
					if (j != x && j != i)
					{
						son[0][j].insert(i);
						son[0][i].insert(j);
						res = min(res, check(i) + 1);
						son[0][i].erase(j);
						son[0][j].erase(i);
					}
				son[0][x].insert(i);
				son[0][i].insert(x);
			}
		if (res == INF) res = -1;
		printf("%d\n", res);
		for (int i = 1; i <= n; i++)
		{
			son[0][i].clear();
			son[1][i].clear();
		}
	}
}