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 fixed fixed_
using namespace std;

int T, n, fa1[55], fa2[55], ind[55];
bool fixed[55];
vector<int> g1[55], g2[55], g[55];

void dfs1(int u) {
	for (int v : g1[u])
		if (v != fa1[u]) {
			fa1[v] = u;
			dfs1(v);
		}
}
void dfs2(int u) {
	for (int v : g2[u])
		if (v != fa2[u]) {
			fa2[v] = u;
			dfs2(v);
		}
}
void dfs3(int u) {
	fixed[u] = true;
	vector<int> tmp(g1[u].size() + g2[u].size());
	merge(g1[u].begin(), g1[u].end(), g2[u].begin(), g2[u].end(), tmp.begin());
	for (int i = 1; i < tmp.size(); ++i)
		if (tmp[i] == tmp[i - 1] && tmp[i] != fa1[u]) dfs3(tmp[i]);
}

int solve(int rt) {
	for (int i = 1; i <= n; ++i) g[i].clear(), ind[i] = fixed[i] = 0;
	fa1[rt] = 0, dfs1(rt);
	fa2[rt] = 0, dfs2(rt);
	dfs3(rt);
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		if (i == rt) continue;
		if (fa1[i] == fa2[i]) {
			if (!fixed[i]) return n;
			continue;
		}
		++cnt;
		if (!fixed[fa1[i]]) g[i].push_back(fa1[i]), ++ind[fa1[i]];
		if (!fixed[fa2[i]]) g[fa2[i]].push_back(i), ++ind[i];
	}
	static int q[55];
	int st = 0, ed = 0;
	for (int i = 1; i <= n; ++i) if (!ind[i]) q[ed++] = i;
	while (st < ed) {
		int u = q[st++];
		for (int v : g[u]) if (!--ind[v]) q[ed++] = v;
	}
	return ed == n ? cnt : n;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) g1[i].clear(), g2[i].clear();
		set<pair<int, int>> s1, s2;
		for (int i = 1, x, y; i < n; ++i) {
			scanf("%d%d", &x, &y);
			if (x > y) swap(x, y);
			s1.emplace(x, y);
			g1[x].push_back(y), g1[y].push_back(x);
		}
		for (int i = 1, x, y; i < n; ++i) {
			scanf("%d%d", &x, &y);
			if (x > y) swap(x, y);
			s2.emplace(x, y);
			g2[x].push_back(y), g2[y].push_back(x);
		}
		if (s1 == s2) {
			puts("0");
			continue;
		}
		for (int i = 1; i <= n; ++i) sort(g1[i].begin(), g1[i].end()), sort(g2[i].begin(), g2[i].end());
		int ans = n + 1;
		for (int rt = 1; rt <= n; ++rt)
			if (g1[rt].size() == 1) {
				int v = g1[rt][0];
				g1[rt].clear();
				g1[v].erase(lower_bound(g1[v].begin(), g1[v].end(), rt));
				for (int i = 1; i <= n; ++i) {
					if (i == v) continue;
					g1[rt] = {i};
					g1[i].insert(lower_bound(g1[i].begin(), g1[i].end(), rt), rt);
					ans = min(ans, 1 + solve(rt));
					g1[i].erase(lower_bound(g1[i].begin(), g1[i].end(), rt));
					g1[rt].clear();
				}
				g1[rt] = {v};
				g1[v].insert(lower_bound(g1[v].begin(), g1[v].end(), rt), rt);
			}
		if (ans > n) ans = -1;
		printf("%d\n", ans);
	}
}