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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int N(55);
struct edge { int x, y; } e[N];
std::vector<int> A[N], B[N], G[N];
int T, n, fa[N], fb[N], deg[N], d[N], pre[N], ans;

void dfs(int x, std::vector<int> *v, int *f)
	{ for (auto i : v[x]) if (i != f[x]) f[i] = x, dfs(i, v, f); }

int main()
{
	for (T = read(); T--; )
	{
		n = read(), ans = n + 1;
		std::memset(deg, 0, (n + 1) << 2);
		std::memset(pre, 0, (n + 1) << 2);
		for (int i = 1; i <= n; i++) A[i].clear();
		for (int i = 1; i <= n; i++) B[i].clear();
		for (int i = 1, a, b; i < n; i++)
			++deg[a = read()], ++deg[b = read()], pre[a] = b, pre[b] = a, e[i] = (edge) {a, b};
		for (int i = 1, a, b; i < n; i++)
			a = read(), b = read(), B[a].push_back(b), B[b].push_back(a);
		for (int x = 1; x <= n; x++) if (deg[x] == 1)
			for (int p = pre[x], y = 1, fl = 1; y <= n; fl = 1, y++) if (y != x)
			{
				for (int i = 1; i <= n; i++) A[i].clear();
				for (int i = 1; i < n; i++) if ((e[i].x != x || e[i].y != p) && (e[i].x != p || e[i].y != x))
					A[e[i].x].push_back(e[i].y), A[e[i].y].push_back(e[i].x);
				A[x].push_back(y), A[y].push_back(x);
				std::memset(fa, 0, (n + 1) << 2), dfs(x, A, fa);
				std::memset(fb, 0, (n + 1) << 2), dfs(x, B, fb);
				for (int i = 1; i <= n; i++)
					if (fa[i] == fb[i] && fa[fa[i]] != fb[fb[i]]) { fl = 0; break; }
				if (!fl) continue;
				for (int i = 1; i <= n; i++) G[i].clear(); std::memset(d, 0, sizeof d);
				for (int i = 1; i <= n; i++) if (fa[i] != fb[i] && fa[fa[i]] != fb[fa[i]]) G[i].push_back(fa[i]), ++d[fa[i]];
				for (int i = 1; i <= n; i++) if (fa[i] != fb[i] && fa[fb[i]] != fb[fb[i]]) G[fb[i]].push_back(i), ++d[i];
				std::queue<int> Q;
				for (int i = 1; i <= n; i++) if (d[i] == 0) Q.push(i);
				while (!Q.empty()) { int x = Q.front(); Q.pop(); for (auto i : G[x]) if (!--d[i]) Q.push(i); }
				for (int i = 1; i <= n; i++) if (d[i]) { fl = 0; break; }
				if (!fl) continue;
				int sum = 0;
				for (int i = 1; i <= n; i++) sum += fa[i] != fb[i];
				ans = std::min(ans, sum + (p != y));
			}
		if (ans == n + 1) ans = -1;
		printf("%d\n", ans);
	}
	return 0;
}