#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define maxv 58
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
vector<int> gr[maxv],rgr[maxv];
vector<int> vs;
bool sumi[maxv];
int cmp[maxv];
void dfs(int v){
	sumi[v]=true;
	rep(i,gr[v].size()){
		if(!sumi[gr[v][i]]) dfs(gr[v][i]);
	}
	vs.pb(v);
}
void rdfs(int v,int k){
	sumi[v]=true;cmp[v]=k;
	rep(i,rgr[v].size()){
		if(!sumi[rgr[v][i]]) rdfs(rgr[v][i],k);
	}
}
int scc(int v)
{
	memset(sumi,false,sizeof(sumi));
	vs.clear();
	rep(i,v){
		if(!sumi[i]) dfs(i);
	}
	memset(sumi,false,sizeof(sumi));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!sumi[vs[i]]) rdfs(vs[i],k++);
	}
	return k;
}
void aedge(int v,int w){
	gr[v].pb(w);rgr[w].pb(v);
}

int st=-1,ko;
vector<int> ed[58][2];
void rec(int v,int u,int d){
	//cout<<v<<u<<d<<endl;
	if(d==0 && v==st) return;
	if(d<0){
		ko++;
		int it=0,i2=0,n=ed[v][0].size()-1,m=ed[v][1].size()-1;
		while(it<n || i2<m){
			int x=ed[v][0][it],y=ed[v][1][i2];
			assert(x!=58 || y!=58);
			if(x==u){
				it++;
			}
			else if(y==u){
				i2++;
			}
			else if(x==st){
				//rec(st,v,0);
				it++;
			}
			else if(x<y){
				rec(x,v,0);it++;
			}
			else if(x>y){
				rec(y,v,1);i2++;
			}
			else{
				assert(x==y);
				rec(x,v,-1);it++;i2++;
			}
		}
	}
	else{
		rep(i,ed[v][d].size()-1){
			int w=ed[v][d][i];
			if(u==w) continue;
			if(d==0) aedge(w,v);else aedge(v,w);
			rec(w,v,d);
		}
	}
}
int cal2(int i,int n){
	//cout<<i<<' '<<st<<endl;
	rep(j,58) gr[j].clear(),rgr[j].clear();
	ko=0;
	rec(i,-1,-1);
	if(scc(n)==n) return n-ko;return 58;
}
int cal(){
	int n,a,b;
	rep(i,55) rep(j,2) ed[i][j].clear();
	cin>>n;
	rep(j,2) rep(i,n-1){
		cin>>a>>b;a--;b--;
		ed[a][j].pb(b);ed[b][j].pb(a);
	}
	int ret=58;st=-1;
	rep(i,n){
		sort(All(ed[i][0]));sort(All(ed[i][1]));
		ed[i][0].pb(58);
		ed[i][1].pb(58);
	}
	rep(i,n){
		ret=min(ret,cal2(i,n));
	}
	int nowret=ret;
	//cout<<"a"<<endl;
	rep(i,n){
		if(ed[i][0].size()>2) continue;
		int ori=ed[i][0][0];
		st=i;
		rep(j,n){
			if(j==i || j==ori) continue;
			ed[i][0][0]=j;
			ret=min(ret,cal2(i,n)+1);
		}
		ed[i][0][0]=ori;
	}
	assert(nowret!=n);
	assert(nowret<n || ret>=n);
	if(ret>50) return -1;
	return ret;
}
int main()
{
	int t;
	cin>>t;
	rep(i,t) cout<<cal()<<endl;
}

### 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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define maxv 58
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
vector<int> gr[maxv],rgr[maxv];
vector<int> vs;
bool sumi[maxv];
int cmp[maxv];
void dfs(int v){
	sumi[v]=true;
	rep(i,gr[v].size()){
		if(!sumi[gr[v][i]]) dfs(gr[v][i]);
	}
	vs.pb(v);
}
void rdfs(int v,int k){
	sumi[v]=true;cmp[v]=k;
	rep(i,rgr[v].size()){
		if(!sumi[rgr[v][i]]) rdfs(rgr[v][i],k);
	}
}
int scc(int v)
{
	memset(sumi,false,sizeof(sumi));
	vs.clear();
	rep(i,v){
		if(!sumi[i]) dfs(i);
	}
	memset(sumi,false,sizeof(sumi));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!sumi[vs[i]]) rdfs(vs[i],k++);
	}
	return k;
}
void aedge(int v,int w){
	gr[v].pb(w);rgr[w].pb(v);
}

int st=-1,ko;
vector<int> ed[58][2];
void rec(int v,int u,int d){
	//cout<<v<<u<<d<<endl;
	if(d==0 && v==st) return;
	if(d<0){
		ko++;
		int it=0,i2=0,n=ed[v][0].size()-1,m=ed[v][1].size()-1;
		while(it<n || i2<m){
			int x=ed[v][0][it],y=ed[v][1][i2];
			assert(x!=58 || y!=58);
			if(x==u){
				it++;
			}
			else if(y==u){
				i2++;
			}
			else if(x==st){
				//rec(st,v,0);
				it++;
			}
			else if(x<y){
				rec(x,v,0);it++;
			}
			else if(x>y){
				rec(y,v,1);i2++;
			}
			else{
				assert(x==y);
				rec(x,v,-1);it++;i2++;
			}
		}
	}
	else{
		rep(i,ed[v][d].size()-1){
			int w=ed[v][d][i];
			if(u==w) continue;
			if(d==0) aedge(w,v);else aedge(v,w);
			rec(w,v,d);
		}
	}
}
int cal2(int i,int n){
	//cout<<i<<' '<<st<<endl;
	rep(j,58) gr[j].clear(),rgr[j].clear();
	ko=0;
	rec(i,-1,-1);
	if(scc(n)==n) return n-ko;return 58;
}
int cal(){
	int n,a,b;
	rep(i,55) rep(j,2) ed[i][j].clear();
	cin>>n;
	rep(j,2) rep(i,n-1){
		cin>>a>>b;a--;b--;
		ed[a][j].pb(b);ed[b][j].pb(a);
	}
	int ret=58;st=-1;
	rep(i,n){
		sort(All(ed[i][0]));sort(All(ed[i][1]));
		ed[i][0].pb(58);
		ed[i][1].pb(58);
	}
	rep(i,n){
		ret=min(ret,cal2(i,n));
	}
	int nowret=ret;
	//cout<<"a"<<endl;
	rep(i,n){
		if(ed[i][0].size()>2) continue;
		int ori=ed[i][0][0];
		st=i;
		rep(j,n){
			if(j==i || j==ori) continue;
			ed[i][0][0]=j;
			ret=min(ret,cal2(i,n)+1);
		}
		ed[i][0][0]=ori;
	}
	assert(nowret!=n);
	assert(nowret<n || ret>=n);
	if(ret>50) return -1;
	return ret;
}
int main()
{
	int t;
	cin>>t;
	rep(i,t) cout<<cal()<<endl;
}

```