#include <algorithm> 
#include <cstdio> 
#include <cstring>
#include <iostream>
#include <vector>

#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline char nc()
{
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f;
}

const int maxn = 50 + 5;
int T;
int N;
struct node
{
	int u, v;
	node(int u=0,int v=0)
	{
		if(u > v) swap(u, v);
		this->u = u;
		this->v = v; 
	}
	bool operator < (const node &other) const
	{
		if(u != other.u) return u < other.u;
		return v < other.v;
	}
};
node a[maxn], b[maxn];

int deg[maxn];
int head[maxn];
struct edge
{
	int to, nex;
	edge(int to=0,int nex=0):to(to),nex(nex){}
};
vector<edge> G;
inline void addedge(int u, int v)
{
	G.push_back(edge(v, head[u])), head[u] = G.size() - 1;
	++deg[v];
}
bool topsort()
{
	static int q[maxn]; int hd = 0, tl = 0;
	for(int i = 1; i <= N; ++i)
	{
		if(deg[i] == 0) q[tl++] = i;
	}
	while(hd < tl)
	{
		int u = q[hd++];
		for(int i = head[u]; ~i; i = G[i].nex)
		{
			int v = G[i].to;
			if(--deg[v] == 0) q[tl++] = v;
		}
	}
	return tl == N;
}

int adj[maxn][maxn];
bool vis[maxn];
vector<int> V;
vector<int> A[maxn];
vector<int> B[maxn];
void travel(int u)
{
	if(vis[u]) return;
	vis[u] = 1;
	V.push_back(u);
	for(unsigned int i = 0; i < A[u].size(); ++i)
	{
		int v = A[u][i]; if(adj[u][v] < 2) continue;
		travel(v);
	}
}
void dfsA(int u, int fa)
{
	for(unsigned int i = 0; i < A[u].size(); ++i)
	{
		int v = A[u][i]; if(v == fa) continue;
		dfsA(v, u);
		addedge(v, u);
	}
}
void dfsB(int u, int fa)
{
	for(unsigned int i = 0; i < B[u].size(); ++i)
	{
		int v = B[u][i]; if(v == fa) continue;
		dfsB(v, u);
		addedge(u, v); 
	}
}
int sol(int r)
{
	memset(adj, 0, sizeof(adj));
	for(int i = 1; i <= N; ++i)
	{
		A[i].clear();
		B[i].clear();
	}
	for(int i = 1; i < N; ++i)
	{
		int u = a[i].u, v = a[i].v;
		A[u].push_back(v);
		A[v].push_back(u);
		++adj[u][v], ++adj[v][u];
	}
	for(int i = 1; i < N; ++i)
	{
		int u = b[i].u, v = b[i].v;
		B[u].push_back(v);
		B[v].push_back(u);
		++adj[u][v], ++adj[v][u];
	}
	V.clear();
	memset(vis, 0, sizeof(vis));
	travel(r); 
	memset(deg, 0, sizeof(deg));
	memset(head, -1, sizeof(head));
	G.clear();
	for(unsigned int i = 0; i < V.size(); ++i)
	{
		int u = V[i];
		for(unsigned int i = 0; i < A[u].size(); ++i)
		{
			int v = A[u][i]; if(vis[v]) continue;
			dfsA(v, u);
		}
		for(unsigned int i = 0; i < B[u].size(); ++i)
		{
			int v = B[u][i]; if(vis[v]) continue;
			dfsB(v, u);
		}
	}
	return topsort() ? N - V.size() : -1;
}

int da[maxn];
int main()
{
	read(T);
	while(T--)
	{
		read(N);
		memset(da, 0, sizeof(da));
		for(int i = 1; i < N; ++i)
		{
			int u, v; read(u), read(v);
			a[i] = node(u, v);
			++da[u], ++da[v];
		}
		for(int i = 1; i < N; ++i)
		{
			int u, v; read(u), read(v);
			b[i] = node(u, v); 
		}
		sort(a + 1, a + N);
		sort(b + 1, b + N);
		bool flag = true;
		for(int i = 1; i < N; ++i)
		{
			if(a[i].u != b[i].u || a[i].v != b[i].v)
			{
				flag = false;
				break;
			}
		}
		if(flag) 
		{
			puts("0");
			continue;
		}
		int an = -1;
		for(int i = 1; i <= N; ++i) if(da[i] == 1)
		{
			int k = -1, v = -1;
			for(int j = 1; j < N; ++j)
			{
				if(a[j].u == i || a[j].v == i) 
				{
					k = j, v = a[j].u + a[j].v - i; 
					break;
				}
			}
			for(int j = 1; j <= N; ++j) if(j != i && j != v)
			{
				a[0] = node(i, j);
				swap(a[0], a[k]);
				int d = sol(i);
				if(d != -1)
				{
//					debug("-- %d\n", i);
//					for(int i = 1; i < N; ++i)
//					{
//						debug("%d %d\n", a[i].u, a[i].v);
//					}
//					debug("\n");
//					for(int i = 1; i < N; ++i)
//					{
//						debug("%d %d\n", b[i].u, b[i].v);
//					}
					++d;
					if(an == -1 || an > d) an = d;
				}
				swap(a[0], a[k]);
			}
		}
		printf("%d\n", an);
	}
	return 0;
}
### 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 <algorithm> 
#include <cstdio> 
#include <cstring>
#include <iostream>
#include <vector>

#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline char nc()
{
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f;
}

const int maxn = 50 + 5;
int T;
int N;
struct node
{
	int u, v;
	node(int u=0,int v=0)
	{
		if(u > v) swap(u, v);
		this->u = u;
		this->v = v; 
	}
	bool operator < (const node &other) const
	{
		if(u != other.u) return u < other.u;
		return v < other.v;
	}
};
node a[maxn], b[maxn];

int deg[maxn];
int head[maxn];
struct edge
{
	int to, nex;
	edge(int to=0,int nex=0):to(to),nex(nex){}
};
vector<edge> G;
inline void addedge(int u, int v)
{
	G.push_back(edge(v, head[u])), head[u] = G.size() - 1;
	++deg[v];
}
bool topsort()
{
	static int q[maxn]; int hd = 0, tl = 0;
	for(int i = 1; i <= N; ++i)
	{
		if(deg[i] == 0) q[tl++] = i;
	}
	while(hd < tl)
	{
		int u = q[hd++];
		for(int i = head[u]; ~i; i = G[i].nex)
		{
			int v = G[i].to;
			if(--deg[v] == 0) q[tl++] = v;
		}
	}
	return tl == N;
}

int adj[maxn][maxn];
bool vis[maxn];
vector<int> V;
vector<int> A[maxn];
vector<int> B[maxn];
void travel(int u)
{
	if(vis[u]) return;
	vis[u] = 1;
	V.push_back(u);
	for(unsigned int i = 0; i < A[u].size(); ++i)
	{
		int v = A[u][i]; if(adj[u][v] < 2) continue;
		travel(v);
	}
}
void dfsA(int u, int fa)
{
	for(unsigned int i = 0; i < A[u].size(); ++i)
	{
		int v = A[u][i]; if(v == fa) continue;
		dfsA(v, u);
		addedge(v, u);
	}
}
void dfsB(int u, int fa)
{
	for(unsigned int i = 0; i < B[u].size(); ++i)
	{
		int v = B[u][i]; if(v == fa) continue;
		dfsB(v, u);
		addedge(u, v); 
	}
}
int sol(int r)
{
	memset(adj, 0, sizeof(adj));
	for(int i = 1; i <= N; ++i)
	{
		A[i].clear();
		B[i].clear();
	}
	for(int i = 1; i < N; ++i)
	{
		int u = a[i].u, v = a[i].v;
		A[u].push_back(v);
		A[v].push_back(u);
		++adj[u][v], ++adj[v][u];
	}
	for(int i = 1; i < N; ++i)
	{
		int u = b[i].u, v = b[i].v;
		B[u].push_back(v);
		B[v].push_back(u);
		++adj[u][v], ++adj[v][u];
	}
	V.clear();
	memset(vis, 0, sizeof(vis));
	travel(r); 
	memset(deg, 0, sizeof(deg));
	memset(head, -1, sizeof(head));
	G.clear();
	for(unsigned int i = 0; i < V.size(); ++i)
	{
		int u = V[i];
		for(unsigned int i = 0; i < A[u].size(); ++i)
		{
			int v = A[u][i]; if(vis[v]) continue;
			dfsA(v, u);
		}
		for(unsigned int i = 0; i < B[u].size(); ++i)
		{
			int v = B[u][i]; if(vis[v]) continue;
			dfsB(v, u);
		}
	}
	return topsort() ? N - V.size() : -1;
}

int da[maxn];
int main()
{
	read(T);
	while(T--)
	{
		read(N);
		memset(da, 0, sizeof(da));
		for(int i = 1; i < N; ++i)
		{
			int u, v; read(u), read(v);
			a[i] = node(u, v);
			++da[u], ++da[v];
		}
		for(int i = 1; i < N; ++i)
		{
			int u, v; read(u), read(v);
			b[i] = node(u, v); 
		}
		sort(a + 1, a + N);
		sort(b + 1, b + N);
		bool flag = true;
		for(int i = 1; i < N; ++i)
		{
			if(a[i].u != b[i].u || a[i].v != b[i].v)
			{
				flag = false;
				break;
			}
		}
		if(flag) 
		{
			puts("0");
			continue;
		}
		int an = -1;
		for(int i = 1; i <= N; ++i) if(da[i] == 1)
		{
			int k = -1, v = -1;
			for(int j = 1; j < N; ++j)
			{
				if(a[j].u == i || a[j].v == i) 
				{
					k = j, v = a[j].u + a[j].v - i; 
					break;
				}
			}
			for(int j = 1; j <= N; ++j) if(j != i && j != v)
			{
				a[0] = node(i, j);
				swap(a[0], a[k]);
				int d = sol(i);
				if(d != -1)
				{
//					debug("-- %d\n", i);
//					for(int i = 1; i < N; ++i)
//					{
//						debug("%d %d\n", a[i].u, a[i].v);
//					}
//					debug("\n");
//					for(int i = 1; i < N; ++i)
//					{
//						debug("%d %d\n", b[i].u, b[i].v);
//					}
					++d;
					if(an == -1 || an > d) an = d;
				}
				swap(a[0], a[k]);
			}
		}
		printf("%d\n", an);
	}
	return 0;
}
```