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 inf 0x3f3f3f3f

using namespace std;

vector <int> e1[55],e2[55],e3[55];
int d1[55],d2[55];

int p1[55],p2[55];

void dfs1(int x) {
  for(int i=0;i<e2[x].size();i++)
    if (e2[x][i]!=p1[x]) {
    	int u=e2[x][i];
    	p1[u]=x;
    	dfs1(u);
	}
}

void dfs2(int x) {
  for(int i=0;i<e3[x].size();i++)
    if (e3[x][i]!=p2[x]) {
    	int u=e3[x][i];
    	p2[u]=x;
    	dfs2(u);
	}
}

vector <int> ee[55];
int deg[55];
queue <int> q;

int solve(int n,int rt) {
  p1[rt]=p2[rt]=0;
  dfs1(rt);
  dfs2(rt);
  int s=0;
  for(int i=1;i<=n;i++) ee[i].clear();
  memset(deg,0,sizeof(deg));
  for(int i=1;i<=n;i++)
    if (p1[i]==p2[i]&&p1[p1[i]]!=p2[p1[i]]) return inf;
  for(int i=1;i<=n;i++)
    if (p1[i]!=p2[i]) {
    	s++;
    	for(int j=0;j<e2[i].size();j++)
    	  if (e2[i][j]!=p1[i]) {
		    ee[e2[i][j]].push_back(i);
		    deg[i]++;
		  }
		for(int j=0;j<e3[i].size();j++)
		  if (e3[i][j]!=p2[i]) {
		    ee[i].push_back(e3[i][j]); 
		    deg[e3[i][j]]++;
		  }
	}
  for(int i=1;i<=n;i++)
    if (!deg[i]) q.push(i);
  while (!q.empty()) {
  	int x=q.front();q.pop();
  	for(int i=0;i<ee[x].size();i++) {
  		int u=ee[x][i];
  		deg[u]--;
  		if (!deg[u]) q.push(u);
	  }
  }
  for(int i=1;i<=n;i++)
    if (deg[i]) return inf;
  return s;
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
  	memset(d1,0,sizeof(d1));
  	memset(d2,0,sizeof(d2));
  	int n;
  	scanf("%d",&n);
  	for(int i=1;i<=n;i++) {
  		e1[i].clear();
  		e2[i].clear();
	  }
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		e2[x].push_back(y);
		e2[y].push_back(x);
		d1[x]++;d1[y]++;
	}
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		e1[x].push_back(y);
		e1[y].push_back(x);
		d2[x]++;d2[y]++;
	}
	for(int i=1;i<=n;i++) e3[i]=e1[i];
	int ans=inf;
	for(int i=1;i<=n;i++)
	  ans=min(ans,solve(n,i));
	if (ans==inf) {
		for(int i=1;i<=n;i++)
		  if (d2[i]==1) {
		  	for(int j=1;j<=n;j++)
		  	  if (j!=i) {
		  	  	  for(int k=1;k<=n;k++) 
					if (k!=i) {
		  	  	  	    e3[k].clear();
		  	  	  	    for(int l=0;l<e1[k].size();l++)
		  	  	  	      if (e1[k][l]!=i) e3[k].push_back(e1[k][l]);
					  }
				  e3[j].push_back(i);
				  e3[i].clear();
				  e3[i].push_back(j);
				  ans=min(ans,solve(n,i)+1);
				}
		  }
	}
	printf("%d\n",(ans<inf)?ans:-1);
  }
  return 0;
}