#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int T,n;
set<int> s1[233],s2[233];
void adde(set<int>*v,int a,int b)
{v[a].insert(b); v[b].insert(a);}
void dele(set<int>*v,int a,int b)
{v[a].erase(b); v[b].erase(a);}
int C=0,a1[SZ],b1[SZ],a2[SZ],b2[SZ];
bool good[SZ];
int gans(int x,int f=0)
{
	int s=1; good[x]=1;
	for(auto b:s1[x])
		if(b!=f&&s2[x].count(b)) s+=gans(b,x);
	return s;
}
vector<int> e3[SZ]; int d[SZ];
void dfs(set<int>*e,int*a,int*b,int c,int x,int f=0)
{
	a[x]=++C;
	for(auto t:e[x]) if(t!=f)
	{
		if(!good[t]&&!good[x])
		{
			if(c) e3[x].pb(t),++d[t];
			else e3[t].pb(x),++d[x];
		}
		dfs(e,a,b,c,t,x);
	}
	b[x]=C;
}
int calc(int t)
{
	for(int i=1;i<=n;++i) good[i]=d[i]=0,e3[i].clear();
	int u=n-gans(t);
	dfs(s1,a1,b1,0,t);
	dfs(s2,a2,b2,1,t);
	queue<int> q;
	for(int i=1;i<=n;++i)
		if(!d[i]) q.push(i);
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		for(auto b:e3[x])
			if(!(--d[b])) q.push(b);
	}
	for(int i=1;i<=n;++i)
		if(d[i]) return 2e9;
	return u;
}
bool vis[SZ];
void ddd(set<int>*e,int x)
{
	vis[x]=1;
	for(auto b:e[x]) if(!vis[b]) ddd(e,b);
}
void sol()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		s1[i].clear(),s2[i].clear();
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(s1,a,b);
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(s2,a,b);
	int ans=2e9;
	for(int i=1;i<=n;++i)
		ans=min(ans,calc(i));
	for(int i=1;i<=n;++i) if(s2[i].size()==1)
	{
		int v=*s2[i].begin();
		dele(s2,i,v);
		for(int j=1;j<=n;++j) if(v!=j)
		{
			adde(s2,i,j);
			for(int k=1;k<=n;++k) vis[k]=0;
			ddd(s2,1);
			bool gg=0;
			for(int k=1;k<=n;++k)
				if(!vis[k]) gg=1;
			if(!gg)
			{
				int w=calc(i);
				if(w==n-1) ans=min(ans,n);
			}
			dele(s2,i,j);
		}
		adde(s2,i,v);
	}
	if(ans>n+2) ans=-1;
	printf("%d\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--) sol();
}

### Prompt

Your challenge is to write 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 <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int T,n;
set<int> s1[233],s2[233];
void adde(set<int>*v,int a,int b)
{v[a].insert(b); v[b].insert(a);}
void dele(set<int>*v,int a,int b)
{v[a].erase(b); v[b].erase(a);}
int C=0,a1[SZ],b1[SZ],a2[SZ],b2[SZ];
bool good[SZ];
int gans(int x,int f=0)
{
	int s=1; good[x]=1;
	for(auto b:s1[x])
		if(b!=f&&s2[x].count(b)) s+=gans(b,x);
	return s;
}
vector<int> e3[SZ]; int d[SZ];
void dfs(set<int>*e,int*a,int*b,int c,int x,int f=0)
{
	a[x]=++C;
	for(auto t:e[x]) if(t!=f)
	{
		if(!good[t]&&!good[x])
		{
			if(c) e3[x].pb(t),++d[t];
			else e3[t].pb(x),++d[x];
		}
		dfs(e,a,b,c,t,x);
	}
	b[x]=C;
}
int calc(int t)
{
	for(int i=1;i<=n;++i) good[i]=d[i]=0,e3[i].clear();
	int u=n-gans(t);
	dfs(s1,a1,b1,0,t);
	dfs(s2,a2,b2,1,t);
	queue<int> q;
	for(int i=1;i<=n;++i)
		if(!d[i]) q.push(i);
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		for(auto b:e3[x])
			if(!(--d[b])) q.push(b);
	}
	for(int i=1;i<=n;++i)
		if(d[i]) return 2e9;
	return u;
}
bool vis[SZ];
void ddd(set<int>*e,int x)
{
	vis[x]=1;
	for(auto b:e[x]) if(!vis[b]) ddd(e,b);
}
void sol()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		s1[i].clear(),s2[i].clear();
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(s1,a,b);
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(s2,a,b);
	int ans=2e9;
	for(int i=1;i<=n;++i)
		ans=min(ans,calc(i));
	for(int i=1;i<=n;++i) if(s2[i].size()==1)
	{
		int v=*s2[i].begin();
		dele(s2,i,v);
		for(int j=1;j<=n;++j) if(v!=j)
		{
			adde(s2,i,j);
			for(int k=1;k<=n;++k) vis[k]=0;
			ddd(s2,1);
			bool gg=0;
			for(int k=1;k<=n;++k)
				if(!vis[k]) gg=1;
			if(!gg)
			{
				int w=calc(i);
				if(w==n-1) ans=min(ans,n);
			}
			dele(s2,i,j);
		}
		adde(s2,i,v);
	}
	if(ans>n+2) ans=-1;
	printf("%d\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--) sol();
}

```