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 pb push_back
#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 55;

int n, cnt;
vector<int> A[N], B[N];

int fa[N], fab[N], deg[N];
bool bad[N];

void DFS_init(int o, bool cur = true) {
	if (cur) ++cnt;
	bad[o] = !cur, deg[o] = 0;
	for (int v : A[o]) {
		if (v == fa[o]) continue;
		fa[v] = o;
		bool flag = cur;
		if (flag) flag &= find(B[o].begin(), B[o].end(), v) != B[o].end();
		DFS_init(v, flag);
		++deg[o];
	}
}

void DFS_getfa(int o) {
	for (int v : B[o]) {
		if (v == fab[o]) continue;
		fab[v] = o;
		DFS_getfa(v);
	}
}

int ans;

int work(int i) {
	cnt = 0;
	fa[i] = 0;
	DFS_init(i);
	if (cnt < ans) return -1;
	fab[i] = 0;
	DFS_getfa(i);

	set<int> S;
	For(j, 1, n) if (bad[j] && !deg[j]) S.insert(j);
	while (true) {
		int o = -1;
		for (int x : S) if (!bad[fab[x]]) { o = x; break; }
		if (o == -1) break;
		S.erase(o), bad[o] = false;
		if (bad[fa[o]] && !--deg[fa[o]]) S.insert(fa[o]);
	}
	For(j, 1, n) if (bad[j]) { cnt = -1; break; }
	return cnt;
}

void del(vector<int> &vec, int x) {
	vec.erase(find(vec.begin(), vec.end(), x));
}

int main() {

	int Case;
	scanf("%d", &Case);
	while (Case--) {

		scanf("%d", &n);
		For(i, 1, n) A[i].clear(), B[i].clear();
		For(i, 2, n) {
			int u, v;
			scanf("%d%d", &u, &v);
			A[u].pb(v), A[v].pb(u);
		}
		For(i, 2, n) {
			int u, v;
			scanf("%d%d", &u, &v);
			B[u].pb(v), B[v].pb(u);
		}

		ans = -1;
		For(i, 1, n) ans = max(ans, work(i));

		if (ans == -1) {
			For(i, 1, n) if (A[i].size() == 1u) {
				int v = A[i][0];
				del(A[i], v), del(A[v], i);
				For(j, 1, n) if (j != i && j != v) {
					A[i].pb(j), A[j].pb(i);
					ans = max(ans, work(i) - 1);
					del(A[i], j), del(A[j], i);
				}
				A[i].pb(v), A[v].pb(i);
			}
		}

		printf("%d\n", ans == -1 ? -1 : n - ans);

	}

	return 0;
}