#include <bits/stdc++.h>

#define F(i, a, b) for (int i = a; i <= b; i ++)
#define G(i, a, b) for (int i = a; i >= b; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mem(a, b) memset(a, b, sizeof a)
#define mec(a, b) memcpy(a, b, sizeof a)
#define out4(x, y, z, w) { printf(#x" = "), W(x), printf(" "#y" = "), W(y), printf(" "#z" = "), W(z), printf(" "#w" = "), W(w), putc('\n'); }
#define out3(x, y, z) { printf(#x" = "), W(x), printf(" "#y" = "), W(y), printf(" "#z" = "), W(z), putc('\n'); }
#define out2(x, y) { printf(#x" = "), W(x), printf(" "#y" = "), W(y), putc('\n'); }
#define out1(x) { printf(#x" = "), W(x), putc('\n'); }
#define outline(x) { puts("-------------------------------------------"#x"----------------------------------------"); }
#define outarr(a, L, R) { printf(#a"[%d..%d] = ", L, R); F(i, L, R) W(a[i]), putc(' '); putc('\n'); }
#define mx(a, b) ((a) = max(a, b))
#define mn(a, b) ((a) = min(a, b))
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((max(x, - (x))))
#define get getchar()
#define pb push_back
#define putc putchar

template <typename Int>
void R(Int &x) {
	char c = get; x = 0; Int t = 1;
	for (; !isdigit(c); c = get) t = (c == '-' ? - 1 : t);
	for (; isdigit(c); x = (x << 3) + (x << 1) + c - '0', c = get); x *= t;
}
template <typename Int>
void W(Int x) {
	if (x < 0) { putc('-'); x = - x ; }
	if (x > 9) W(x / 10); putc(x % 10 + '0');
}

using namespace std;

const int N = 51;
int TT, n, u, v, L, Len, flag;
int Q[N], C[N], E[N][N], vis[N];
struct node { int x, y; };
multiset <int> A[N], B[N];
multiset <int> :: iterator it;

int Doit(int Root) {
//	out1(Root);
	mem(vis, 0);
	C[Len = 1] = Root, vis[Root] = 1;
	while (1) {
		flag = 0;
		F(k, 1, n) if (!vis[k]) {
			F(p, 1, Len)
				if (E[k][C[p]] && A[C[p]].find(k) != A[C[p]].end()) {
					C[++ Len] = k, vis[k] = flag = 1;
					break;
				}
		}
		if (!flag) break;
	}
//	outarr(C, 1, Len);
	L = 0;
	F(k, 1, n)
		if (k != Root && A[k].size() == 1 && !vis[k])
			Q[++ L] = k;
	int cnt = 0;
	while (L) {
//		outarr(Q, 1, L);
		cnt ++;
		F(i, 1, L) {
			int k = Q[i], pt = 0;
			flag = 0;
			F(j, 1, Len)
				if (E[k][C[j]]) {
					flag ++;
					pt = C[j];
				}
//			if (!flag) {
//				if (E[k][*A[k].begin()])
//					flag = 1, pt = *A[k].begin();
//			}
//			assert(flag <= 1);
			if (flag) {
//				assert(pt != 0);
				if (A[k].find(pt) != A[k].end())
					cnt --;
				else {
					it = A[k].begin(); int p = *it;
					A[p].erase(k);
					A[k].erase(p);
//					out1(cnt);
//					out4(k, p, pt, A[p].size());
//					outarr(vis, 1, n);
					if (!vis[p] && A[p].size() == 1)
						Q[++ L] = p;
					A[k].insert(pt);
					A[pt].insert(k);
				}
				C[++ Len] = k, vis[k] = 1;
				if (i == L) L --; else Q[i] = Q[L --];
				break;
			}
		}
		if (!flag) {
			cnt --;
			break;
		}
	}

	int ct = 0;
	F(k, 1, n)
		for (it = A[k].begin(); it != A[k].end(); it ++)
			ct += E[k][*it];
	if (ct != 2 * (n - 1))
		return 2e9;

	return cnt;
}

int main() {
//	freopen("data.in", "r", stdin);
//	freopen("no.out","w",stdout);

	for (R(TT); TT --; ) {
		R(n), mem(C, 0), mem(E, 0);
		F(i, 1, n) A[i].clear();
		F(i, 1, n - 1) {
			R(u), R(v);
			A[u].insert(v), A[v].insert(u);
		}
		F(i, 1, n - 1) {
			R(u), R(v);
			E[u][v] = E[v][u] = 1;
		}
		int cnt = 0;
		F(k, 1, n)
			for (it = A[k].begin(); it != A[k].end(); it ++)
				cnt += E[k][*it];
		if (cnt == 2 * (n - 1)) {
			puts("0");
			continue;
		}

		F(j, 1, n) B[j] = A[j];
		int Ans = 2e9;
		F(i, 1, n) {
			F(j, 1, n) A[j] = B[j];
			int stp = Doit(i);
			mn(Ans, stp);
			if (B[i].size() == 1) {
				F(k, 1, n) {
					F(j, 1, n) A[j] = B[j];
					A[*A[i].begin()].erase(i), A[i].clear();
					A[i].insert(k), A[k].insert(i);
					int stp = Doit(i);
					mn(Ans, stp + 1);
				}
			}
		}
		if (Ans == 2e9)
			Ans = - 1;
		W(Ans), putc('\n');
	}
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>

#define F(i, a, b) for (int i = a; i <= b; i ++)
#define G(i, a, b) for (int i = a; i >= b; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mem(a, b) memset(a, b, sizeof a)
#define mec(a, b) memcpy(a, b, sizeof a)
#define out4(x, y, z, w) { printf(#x" = "), W(x), printf(" "#y" = "), W(y), printf(" "#z" = "), W(z), printf(" "#w" = "), W(w), putc('\n'); }
#define out3(x, y, z) { printf(#x" = "), W(x), printf(" "#y" = "), W(y), printf(" "#z" = "), W(z), putc('\n'); }
#define out2(x, y) { printf(#x" = "), W(x), printf(" "#y" = "), W(y), putc('\n'); }
#define out1(x) { printf(#x" = "), W(x), putc('\n'); }
#define outline(x) { puts("-------------------------------------------"#x"----------------------------------------"); }
#define outarr(a, L, R) { printf(#a"[%d..%d] = ", L, R); F(i, L, R) W(a[i]), putc(' '); putc('\n'); }
#define mx(a, b) ((a) = max(a, b))
#define mn(a, b) ((a) = min(a, b))
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((max(x, - (x))))
#define get getchar()
#define pb push_back
#define putc putchar

template <typename Int>
void R(Int &x) {
	char c = get; x = 0; Int t = 1;
	for (; !isdigit(c); c = get) t = (c == '-' ? - 1 : t);
	for (; isdigit(c); x = (x << 3) + (x << 1) + c - '0', c = get); x *= t;
}
template <typename Int>
void W(Int x) {
	if (x < 0) { putc('-'); x = - x ; }
	if (x > 9) W(x / 10); putc(x % 10 + '0');
}

using namespace std;

const int N = 51;
int TT, n, u, v, L, Len, flag;
int Q[N], C[N], E[N][N], vis[N];
struct node { int x, y; };
multiset <int> A[N], B[N];
multiset <int> :: iterator it;

int Doit(int Root) {
//	out1(Root);
	mem(vis, 0);
	C[Len = 1] = Root, vis[Root] = 1;
	while (1) {
		flag = 0;
		F(k, 1, n) if (!vis[k]) {
			F(p, 1, Len)
				if (E[k][C[p]] && A[C[p]].find(k) != A[C[p]].end()) {
					C[++ Len] = k, vis[k] = flag = 1;
					break;
				}
		}
		if (!flag) break;
	}
//	outarr(C, 1, Len);
	L = 0;
	F(k, 1, n)
		if (k != Root && A[k].size() == 1 && !vis[k])
			Q[++ L] = k;
	int cnt = 0;
	while (L) {
//		outarr(Q, 1, L);
		cnt ++;
		F(i, 1, L) {
			int k = Q[i], pt = 0;
			flag = 0;
			F(j, 1, Len)
				if (E[k][C[j]]) {
					flag ++;
					pt = C[j];
				}
//			if (!flag) {
//				if (E[k][*A[k].begin()])
//					flag = 1, pt = *A[k].begin();
//			}
//			assert(flag <= 1);
			if (flag) {
//				assert(pt != 0);
				if (A[k].find(pt) != A[k].end())
					cnt --;
				else {
					it = A[k].begin(); int p = *it;
					A[p].erase(k);
					A[k].erase(p);
//					out1(cnt);
//					out4(k, p, pt, A[p].size());
//					outarr(vis, 1, n);
					if (!vis[p] && A[p].size() == 1)
						Q[++ L] = p;
					A[k].insert(pt);
					A[pt].insert(k);
				}
				C[++ Len] = k, vis[k] = 1;
				if (i == L) L --; else Q[i] = Q[L --];
				break;
			}
		}
		if (!flag) {
			cnt --;
			break;
		}
	}

	int ct = 0;
	F(k, 1, n)
		for (it = A[k].begin(); it != A[k].end(); it ++)
			ct += E[k][*it];
	if (ct != 2 * (n - 1))
		return 2e9;

	return cnt;
}

int main() {
//	freopen("data.in", "r", stdin);
//	freopen("no.out","w",stdout);

	for (R(TT); TT --; ) {
		R(n), mem(C, 0), mem(E, 0);
		F(i, 1, n) A[i].clear();
		F(i, 1, n - 1) {
			R(u), R(v);
			A[u].insert(v), A[v].insert(u);
		}
		F(i, 1, n - 1) {
			R(u), R(v);
			E[u][v] = E[v][u] = 1;
		}
		int cnt = 0;
		F(k, 1, n)
			for (it = A[k].begin(); it != A[k].end(); it ++)
				cnt += E[k][*it];
		if (cnt == 2 * (n - 1)) {
			puts("0");
			continue;
		}

		F(j, 1, n) B[j] = A[j];
		int Ans = 2e9;
		F(i, 1, n) {
			F(j, 1, n) A[j] = B[j];
			int stp = Doit(i);
			mn(Ans, stp);
			if (B[i].size() == 1) {
				F(k, 1, n) {
					F(j, 1, n) A[j] = B[j];
					A[*A[i].begin()].erase(i), A[i].clear();
					A[i].insert(k), A[k].insert(i);
					int stp = Doit(i);
					mn(Ans, stp + 1);
				}
			}
		}
		if (Ans == 2e9)
			Ans = - 1;
		W(Ans), putc('\n');
	}
}
```