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:
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 50 + 7 ;

int T ;

int n ;
vector <int> g[2][N] ;

int par[2][N] , deg[N] ;
bool mark[2][N] ;
vector <int> child[2][N] ;

inline void init_get () {
	for (int i = 0 ; i < n ; i ++) {
		deg[i] = 0 ;
		for (int id : {0 , 1}) {
			par[id][i] = -1 ;
			mark[id][i] = 0 ;
			child[id][i].clear() ;
		}
	}
}

void pre_dfs (int v , int id) {
	for (int u : g[id][v]) {
		if (u == par[id][v]) continue ;
		par[id][u] = v ;
		child[id][v].push_back(u) ;
		pre_dfs(u , id) ;
	}
}

void dfs (int v) {
	mark[0][v] = mark[1][v] = 1 ;

	for (int u : child[0][v])
		if (v == par[1][u]) dfs(u) ;
}

int sss ;

inline int get (int root) {
	init_get() ;

	for (int id : {0 , 1}) {
		par[id][root] = -1 ;
		pre_dfs(root , id) ;
	}

	dfs(root) ;

	int ans = n ;

	for (int i = 0 ; i < n ; i ++) {
		if (mark[0][i] && mark[1][i]) {
			ans -- ;
			for (int j : child[1][i]) mark[1][j] = 1 ;
		}
	}

	int need = ans ;
	queue <int> que ;

	for (int i = 0 ; i < n ; i ++) {
		if (mark[0][i] && mark[1][i]) continue ;

		deg[i] = child[0][i].size() ;
		if (!deg[i]) {
			mark[0][i] = 1 ;
			if (mark[0][i] && mark[1][i]) que.push(i) ;
		}
	}

	while (_sz(que)) {
		int v = que.front() ;
		que.pop() ;
		need -- ;
	
		for (int u : child[1][v]) {
			mark[1][u] = 1 ;
			if (mark[0][u] && mark[1][u]) que.push(u) ;
		}

		{
			int u = par[0][v] ;
			if (!mark[0][u]) {
				deg[u] -- ;
				if (!deg[u]) mark[0][u] = 1 ;
				if (mark[0][u] && mark[1][u]) que.push(u) ;
			}
		}	
	}

	if (need) ans = n + 5 ;

	if (ans == n + 5 && sss > n && g[1][root].size() == 1) {
		for (int vv = 0 ; vv < n ; vv ++) {
			init_get() ;

			pre_dfs(root , 1) ;
			pre_dfs(vv , 0) ;

			if (child[1][vv].size() || child[0][root].size()) continue ;
			
			for (int i = 0 ; i < n ; i ++) {
				deg[i] = child[0][i].size() ;
				if (!deg[i]) mark[0][i] = 1 ;
			}
	
			mark[0][root] = mark[1][root] = 1 ;
			que.push(root) ;

			need = n ;
			while (_sz(que)) {
				int v = que.front() ;
				que.pop() ;
				need -- ;

				for (int u : child[1][v]) {
					if (mark[0][u] && mark[1][u]) assert(0) ; ;
					mark[1][u] = 1 ;
					if (mark[0][u] && mark[1][u]) que.push(u) ;
				}

				{
					int u = par[0][v] ;
					if (u != -1) {
			//			if (mark[0][u] && mark[1][u]) assert(0) ;

						deg[u] -- ;
						assert(deg[u] >= 0) ;
						if (!deg[u]) mark[0][u] = 1 ;
						if (mark[0][u] && mark[1][u]) que.push(u) ;
					}
				}
			}

			if (!need) ans = n ;
		}
	}

	return ans ;
}

inline void init_solve () {
	init_get() ;
	for (int i = 0 ; i < n ; i ++) g[0][i].clear() , g[1][i].clear() ;
	n = 0 ; // Just for fun 
}

inline void solve () {
	init_solve() ;

	cin >> n ;

	for (int id : {0 , 1}) {
		for (int i = 0 , u , v ; i < n - 1 ; i ++) {
			cin >> u >> v ;
			u -- , v -- ;
			g[id][u].push_back(v) ;
			g[id][v].push_back(u) ;
		}
	}


	sss = n + 5 ;
	for (int i = 0 ; i < n ; i ++) sss = min(sss , get(i)) ;

	if (sss > n) sss = -1 ;

	cout << sss << '\n' ;
}

int main(){
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;

	cin >> T ;

	while (T --) solve() ;
}