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<algorithm>
#include<vector>
using namespace std;
int n, Deg[60], par1[60], par2[60], Num1[60], Ed1[60], Ed2[60], Num2[60], cnt, chk[60], res;
int ww[60][60], GD[60], Q[60];
vector<int>E[60], F[60], G[60];
struct Edge {
	int a, b;
}w[60];
void DFS1(int a, int pp) {
	Num1[a] = ++cnt;
	par1[a] = pp;
	for (auto &x : E[a]) {
		if (x != pp)DFS1(x, a);
	}
	Ed1[a] = cnt;
}
void DFS2(int a, int pp) {
	Num2[a] = ++cnt;
	par2[a] = pp;
	for (auto &x : F[a]) {
		if (x != pp)DFS2(x, a);
	}
	Ed2[a] = cnt;
}
bool OK(int a, int b) {
	int i;
	int c = 0;
	if (ww[a][b] % 2 == 0)c++;
	for (i = 1; i <= n; i++) {
		E[i].clear();
		G[i].clear();
		GD[i] = 0;
		chk[i] = 0;
	}
	for (i = 1; i < n; i++) {
		if (w[i].a == a||w[i].b == a)continue;
		E[w[i].a].push_back(w[i].b);
		E[w[i].b].push_back(w[i].a);
	}
	E[a].push_back(b);
	E[b].push_back(a);
	cnt = 0;
	DFS1(a,0);
	cnt = 0;
	DFS2(a,0);
	for (i = 1; i <= n; i++) {
		if (par1[i] != par2[i])chk[i] = 1;
	}
	for (i = 1; i <= n; i++) {
		if (!chk[i] && chk[par1[i]])return false;
		if (chk[i])c++;
		if (chk[i]) {
			if(chk[par1[i]])G[i].push_back(par1[i]), GD[par1[i]]++;
			G[par2[i]].push_back(i), GD[i]++;
		}
	}
	int head = 0, tail = 0;
	for (i = 1; i <= n; i++)if (!GD[i])Q[++tail] = i;
	while (head < tail) {
		int x = Q[++head];
		for (auto &y : G[x]) {
			GD[y]--;
			if (!GD[y])Q[++tail] = y;
		}
	}
	if (tail != n)return false;
	if (res == -1 || res > c)res = c;
	return true;
}
void Solve() {
	int i, j;
	res = -1;
	for (i = 1; i <= n; i++) {
		if (Deg[i] == 1) {
			for (j = 1; j <= n; j++) {
				if (i != j) {
					OK(i, j);
				}
			}
		}
	}
	printf("%d\n", res);
}
int main() {
	int TC, i, a, b, j;
	scanf("%d", &TC);
	while (TC--) {
		scanf("%d", &n);
		for (i = 1; i <= n; i++) {
			E[i].clear(), F[i].clear();
			for (j = 1; j <= n; j++)ww[i][j] = 0;
			Deg[i] = 0;
		}
		for (i = 1; i < n; i++) {
			scanf("%d%d", &a, &b);
			ww[a][b] ++, ww[b][a]++;
			w[i] = { a,b };
			Deg[a]++, Deg[b]++;
		}
		for (i = 1; i < n; i++) {
			scanf("%d%d", &a, &b);
			ww[a][b] +=2, ww[b][a] +=2;
			F[a].push_back(b);
			F[b].push_back(a);
		}
		int ck = 0;
		for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (ww[i][j]%3)ck = 1;
		if (!ck) {
			puts("0");
			continue;
		}
		Solve();
	}
}