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>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

void DFS(int R, vector< vector<int> > & G, vector<int> & par, vector<int> & seq) {
	seq.push_back(R);
	ALL_THE(G[R], it) if(par[*it] == -1) {
		par[*it] = R;
		DFS(*it, G, par, seq);
	}
}

int min_ops_test(vector< vector<int> > & Gi, vector< vector<int> > & Gt, int R) {
	int N = Gi.size();
	vector<int> pari(N, -1), part(N, -1);
	vector<int> seqi, seqt;
	pari[R] = R;
	DFS(R, Gi, pari, seqi);
	part[R] = R;
	DFS(R, Gt, part, seqt);
	vector<bool> match(N, false); // vertices with already matching path from R
	match[R] = true;
	for(int i = 1; i < N; i++)
		match[seqi[i]] = (pari[seqi[i]] == part[seqi[i]] && match[pari[seqi[i]]]);
	vector<int> deg(N);
	vector<bool> top(N, false), leaf(N, false);
	for(int i = 0; i < N; i++) if(!match[i] && match[part[i]]) top[i] = true;
	for(int i = 0; i < N; i++) deg[i] = Gi[i].size();
	for(int i = 0; i < N; i++) if(deg[i] == 1) leaf[i] = true;
	int cur = 0, req = N;
	for(int i = 0; i < N; i++) req -= match[i];
	for(int i = 0; i < N; i++) {
		bool done = true;
		for(int j = 0; j < N; j++) if(leaf[j] && top[j]) {
			leaf[j] = false;
			deg[pari[j]]--;
			deg[j] = -1;
			if(deg[pari[j]] == 1 && !match[pari[j]]) leaf[pari[j]] = true;
			top[j] = false;
			ALL_THE(Gt[j], it) if(!match[*it]) top[*it] = true;
			match[j] = true;
			done = false;
			cur++;
			break;
		}
		if(done) break;
	}
	if(cur == req) return req;
	return N+1;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int T;
	cin >> T;
	for(int t = 0; t < T; t++) {
		int N;
		cin >> N;
		vector< vector<int> > Gi(N), Gt(N);
		for(int i = 0; i < N-1; i++) {
			int u, v;
			cin >> u >> v;
			Gi[--u].push_back(--v);
			Gi[v].push_back(u);
		}
		for(int i = 0; i < N-1; i++) {
			int u, v;
			cin >> u >> v;
			Gt[--u].push_back(--v);
			Gt[v].push_back(u);
		}
		int ans = N+1;
		for(int r = 0; r < N; r++) ans = min(ans, min_ops_test(Gi, Gt, r));
		if(ans == N+1)
		for(int r = 0; r < N; r++) if((int)Gi[r].size() == 1)
			for(int v = 0; v < N; v++) if(v != r) {
				vector< vector<int> > Gi_moved = Gi;
				int u = Gi[r][0];
				for(int i = 0; i < (int)Gi[u].size(); i++) if(Gi[u][i] == r)
					Gi_moved[u].erase(begin(Gi_moved[u])+i);
				Gi_moved[r][0] = v;
				Gi_moved[v].push_back(r);
				ans = min(ans, min_ops_test(Gi_moved, Gt, r) + 1);
			}
		cout << ((ans == N+1) ? -1 : ans) << "\n";
	}
	return 0;
}

// look at my code
// my code is amazing