#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int q,n;
vvi a,b;
vi vis,d;

void dfs(int v,int t){
	vis[v]=t;
	for(int u=0;u<n;u++) if(a[v][u]&&b[v][u]&&vis[u]==-1) dfs(u,t);
}

int main(){
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>n;
		a=b=vvi(n,vi(n));
		vis=vi(n,-1);
		d=vi(n);
		for(int j=1;j<n;j++){
			int u,v;
			cin>>u>>v;
			u--;v--;
			a[u][v]=a[v][u]=1;
			d[u]++;d[v]++;
		}
		for(int j=1;j<n;j++){
			int u,v;
			cin>>u>>v;
			u--;v--;
			b[u][v]=b[v][u]=1;
		}
		int res=inf,type=0;
		for(int j=0;j<n;j++) if(vis[j]==-1){
			dfs(j,type);
			int cnt=0;
			vi d_=d,used(n);
			vvi a_=a;
			for(int k=0;k<n;k++) if(vis[k]==type){
				cnt++;
				used[k]=1;
			}
			bool flag=1;
			for(int k=0;k<n-cnt;k++){
				bool B=0;
				for(int v=0;v<n;v++) if(d[v]==1&&!used[v]){
					int w;
					for(int u=0;u<n;u++) if(a[v][u]) w=u;
					for(int u=0;u<n;u++) if(used[u]&&b[v][u]){
						a[v][w]--;a[w][v]--;
						a[v][u]++;a[u][v]++;
						d[w]--;d[u]++;
						B=1;used[v]=1;
						break;
					}
					if(B) break;
				}
				if(!B){
					flag=0;
					break;
				}
			}
			if(flag) res=min(res,n-cnt);
			type++;
			d=d_;a=a_;
		}
		for(int j=0;j<n;j++) if(d[j]==1){
			int x;
			for(int k=0;k<n;k++) if(a[j][k]) x=k;
			for(int y=0;y<n;y++){
				vi used(n),d_=d;
				vvi a_=a;
				used[j]=1;
				bool flag=1;
				a[j][x]--;a[x][j]--;
				a[j][y]--;a[y][j]--;
				d[x]--;d[y]++;
				for(int k=0;k<n-1;k++){
					bool B=0;
					for(int v=0;v<n;v++) if(d[v]==1&&!used[v]){
						int w;
						for(int u=0;u<n;u++) if(a[v][u]) w=u;
						for(int u=0;u<n;u++) if(used[u]&&b[v][u]){
							a[v][w]--;a[w][v]--;
							a[v][u]++;a[u][v]++;
							d[w]--;d[u]++;
							B=1;used[v]=1;
							break;
						}
						if(B) break;
					}
					if(!B){
						flag=0;
						break;
					}
				}
				if(flag) res=min(res,n);
				a=a_;d=d_;
			}
		}
		cout<<(res==inf?-1:res)<<endl;
	}
}
### Prompt

In cpp, your task is to solve 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 <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int q,n;
vvi a,b;
vi vis,d;

void dfs(int v,int t){
	vis[v]=t;
	for(int u=0;u<n;u++) if(a[v][u]&&b[v][u]&&vis[u]==-1) dfs(u,t);
}

int main(){
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>n;
		a=b=vvi(n,vi(n));
		vis=vi(n,-1);
		d=vi(n);
		for(int j=1;j<n;j++){
			int u,v;
			cin>>u>>v;
			u--;v--;
			a[u][v]=a[v][u]=1;
			d[u]++;d[v]++;
		}
		for(int j=1;j<n;j++){
			int u,v;
			cin>>u>>v;
			u--;v--;
			b[u][v]=b[v][u]=1;
		}
		int res=inf,type=0;
		for(int j=0;j<n;j++) if(vis[j]==-1){
			dfs(j,type);
			int cnt=0;
			vi d_=d,used(n);
			vvi a_=a;
			for(int k=0;k<n;k++) if(vis[k]==type){
				cnt++;
				used[k]=1;
			}
			bool flag=1;
			for(int k=0;k<n-cnt;k++){
				bool B=0;
				for(int v=0;v<n;v++) if(d[v]==1&&!used[v]){
					int w;
					for(int u=0;u<n;u++) if(a[v][u]) w=u;
					for(int u=0;u<n;u++) if(used[u]&&b[v][u]){
						a[v][w]--;a[w][v]--;
						a[v][u]++;a[u][v]++;
						d[w]--;d[u]++;
						B=1;used[v]=1;
						break;
					}
					if(B) break;
				}
				if(!B){
					flag=0;
					break;
				}
			}
			if(flag) res=min(res,n-cnt);
			type++;
			d=d_;a=a_;
		}
		for(int j=0;j<n;j++) if(d[j]==1){
			int x;
			for(int k=0;k<n;k++) if(a[j][k]) x=k;
			for(int y=0;y<n;y++){
				vi used(n),d_=d;
				vvi a_=a;
				used[j]=1;
				bool flag=1;
				a[j][x]--;a[x][j]--;
				a[j][y]--;a[y][j]--;
				d[x]--;d[y]++;
				for(int k=0;k<n-1;k++){
					bool B=0;
					for(int v=0;v<n;v++) if(d[v]==1&&!used[v]){
						int w;
						for(int u=0;u<n;u++) if(a[v][u]) w=u;
						for(int u=0;u<n;u++) if(used[u]&&b[v][u]){
							a[v][w]--;a[w][v]--;
							a[v][u]++;a[u][v]++;
							d[w]--;d[u]++;
							B=1;used[v]=1;
							break;
						}
						if(B) break;
					}
					if(!B){
						flag=0;
						break;
					}
				}
				if(flag) res=min(res,n);
				a=a_;d=d_;
			}
		}
		cout<<(res==inf?-1:res)<<endl;
	}
}
```