#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=50;

struct T {
	int n;
	vector<int> adj[MAXN];
	bool have(int a,int b) { REPSZ(i,adj[a]) if(adj[a][i]==b) return true; return false; }
	void move(int a,int b) {
		assert(SZ(adj[a])==1);
		int to=adj[a][0]; adj[a].clear(); REPSZ(i,adj[to]) if(adj[to][i]==a) { adj[to].erase(adj[to].begin()+i); break; }
		adj[a].PB(b),adj[b].PB(a);
	}

};

int n;
T A,B;

int solve(T &t,int root) {
	vector<bool> fixed(n,false);
	queue<int> q;
	fixed[root]=true; q.push(root);
	while(!q.empty()) { int at=q.front(); q.pop(); REPSZ(i,t.adj[at]) { int to=t.adj[at][i]; if(!fixed[to]&&B.have(at,to)) { fixed[to]=true; q.push(to); } } }
	//printf("\torig:"); REP(i,n) if(fixed[i]) printf(" %d",i+1); puts("");
	int ret=0;
	vector<vector<int>> after(n);
	REP(at,n) if(!fixed[at]&&SZ(t.adj[at])==1) REPSZ(i,B.adj[at]) { int to=B.adj[at][i]; if(fixed[to]) q.push(at); else after[to].PB(at); }
	while(!q.empty()){ 
		int at=q.front(); q.pop();
		//printf("\tmoving %d\n",at+1);
		assert(!fixed[at]&&SZ(t.adj[at])==1);
		int dst=-1; REPSZ(i,B.adj[at]) { int to=B.adj[at][i]; if(fixed[to]) { assert(dst==-1); dst=to; } } assert(dst!=-1);
		int oth=t.adj[at][0];
		t.move(at,dst); ++ret;
		if(!fixed[oth]&&SZ(t.adj[oth])==1) REPSZ(i,B.adj[oth]) { int to=B.adj[oth][i]; if(fixed[to]) q.push(oth); else after[to].PB(oth); }
		fixed[at]=true; REPSZ(i,after[at]) { int to=after[at][i]; if(!fixed[to]) q.push(to); }
	}
	REP(i,n) if(!fixed[i]) return INT_MAX;
	return ret;
}

int solve() {
	int ret=INT_MAX;
	REP(i,n) { // keep i
		T t=A;
		int cur=solve(t,i);
		ret=min(ret,cur);
	}
	REP(i,n) REP(j,n) if(i!=j) { // first move i to j
		if(SZ(A.adj[i])!=1) continue;
		//printf("moving %d to %d\n",i+1,j+1);
		T t=A; t.move(i,j);
		int cur=solve(t,i);
		if(cur!=INT_MAX) ++cur;
		ret=min(ret,cur);
	}
	return ret==INT_MAX?-1:ret;
}


void run() {
	scanf("%d",&n); A.n=B.n=n;
	REP(i,n-1) { int u,v; scanf("%d%d",&u,&v); --u,--v; A.adj[u].PB(v),A.adj[v].PB(u); }
	REP(i,n-1) { int u,v; scanf("%d%d",&u,&v); --u,--v; B.adj[u].PB(v),B.adj[v].PB(u); }
	printf("%d\n",solve());
	REP(i,n) A.adj[i].clear(),B.adj[i].clear();
}

int main() {
	int n; scanf("%d",&n); FORE(i,1,n) run();
	return 0;
}

### Prompt

Your task is to create a cpp solution to the following 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

### Response

```cpp
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=50;

struct T {
	int n;
	vector<int> adj[MAXN];
	bool have(int a,int b) { REPSZ(i,adj[a]) if(adj[a][i]==b) return true; return false; }
	void move(int a,int b) {
		assert(SZ(adj[a])==1);
		int to=adj[a][0]; adj[a].clear(); REPSZ(i,adj[to]) if(adj[to][i]==a) { adj[to].erase(adj[to].begin()+i); break; }
		adj[a].PB(b),adj[b].PB(a);
	}

};

int n;
T A,B;

int solve(T &t,int root) {
	vector<bool> fixed(n,false);
	queue<int> q;
	fixed[root]=true; q.push(root);
	while(!q.empty()) { int at=q.front(); q.pop(); REPSZ(i,t.adj[at]) { int to=t.adj[at][i]; if(!fixed[to]&&B.have(at,to)) { fixed[to]=true; q.push(to); } } }
	//printf("\torig:"); REP(i,n) if(fixed[i]) printf(" %d",i+1); puts("");
	int ret=0;
	vector<vector<int>> after(n);
	REP(at,n) if(!fixed[at]&&SZ(t.adj[at])==1) REPSZ(i,B.adj[at]) { int to=B.adj[at][i]; if(fixed[to]) q.push(at); else after[to].PB(at); }
	while(!q.empty()){ 
		int at=q.front(); q.pop();
		//printf("\tmoving %d\n",at+1);
		assert(!fixed[at]&&SZ(t.adj[at])==1);
		int dst=-1; REPSZ(i,B.adj[at]) { int to=B.adj[at][i]; if(fixed[to]) { assert(dst==-1); dst=to; } } assert(dst!=-1);
		int oth=t.adj[at][0];
		t.move(at,dst); ++ret;
		if(!fixed[oth]&&SZ(t.adj[oth])==1) REPSZ(i,B.adj[oth]) { int to=B.adj[oth][i]; if(fixed[to]) q.push(oth); else after[to].PB(oth); }
		fixed[at]=true; REPSZ(i,after[at]) { int to=after[at][i]; if(!fixed[to]) q.push(to); }
	}
	REP(i,n) if(!fixed[i]) return INT_MAX;
	return ret;
}

int solve() {
	int ret=INT_MAX;
	REP(i,n) { // keep i
		T t=A;
		int cur=solve(t,i);
		ret=min(ret,cur);
	}
	REP(i,n) REP(j,n) if(i!=j) { // first move i to j
		if(SZ(A.adj[i])!=1) continue;
		//printf("moving %d to %d\n",i+1,j+1);
		T t=A; t.move(i,j);
		int cur=solve(t,i);
		if(cur!=INT_MAX) ++cur;
		ret=min(ret,cur);
	}
	return ret==INT_MAX?-1:ret;
}


void run() {
	scanf("%d",&n); A.n=B.n=n;
	REP(i,n-1) { int u,v; scanf("%d%d",&u,&v); --u,--v; A.adj[u].PB(v),A.adj[v].PB(u); }
	REP(i,n-1) { int u,v; scanf("%d%d",&u,&v); --u,--v; B.adj[u].PB(v),B.adj[v].PB(u); }
	printf("%d\n",solve());
	REP(i,n) A.adj[i].clear(),B.adj[i].clear();
}

int main() {
	int n; scanf("%d",&n); FORE(i,1,n) run();
	return 0;
}

```