#include <bits/stdc++.h>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

vector<pi> readTree(int n){
	vector<pi> a;
	REP(i,n-1){
		int u=read()-1,v=read()-1;
		if(u>v)swap(u,v);
		a.PB(pi(u,v));
	}
	sort(ALL(a));
	return a;
}

bool findEdge(const vector<pi>& b,pi e){
	if(e.first>e.second)
		swap(e.first,e.second);
	auto itr=lower_bound(ALL(b),e);
	if(itr!=b.end()&&*itr==e)
		return true;
	else
		return false;
}

const int Nmax=55;
vi tr[Nmax],bTr[Nmax];
vi ch[Nmax];
int par[Nmax],bPar[Nmax],aliveC[Nmax],st[Nmax],done;
queue<int> qv;
void IncState(int v){
	st[v]++;
	if(st[v]==2)
		qv.push(v);
}
void SetReady(int v,int p){
	done++;
	st[v]=-inf;
	for(auto c:bTr[v])
		if(c!=p){
			IncState(c);
			bPar[c]=v;
		}
}
void dfs(int v,int p,bool fixed,const vector<pi>& b){
	par[v]=p;
	for(auto to:tr[v])
		if(to!=p){
			bool f=fixed&&findEdge(b,pi(v,to));
			ch[v].PB(to);
			aliveC[v]++;
			dfs(to,v,f,b);
		}
	if(fixed)
		SetReady(v,p);
}

int Sub(int n,int root,const vector<pi>& a,const vector<pi>& b){
	cerr<<a<<endl;
	REP(i,n){
		tr[i]=vi();
		bTr[i]=vi();
		ch[i]=vi();
		par[i]=-1;
		bPar[i]=-1;
		aliveC[i]=0;
		st[i]=0;
	}
	done=0;
	qv=queue<int>();
	for(auto e:a){
		tr[e.first].PB(e.second);
		tr[e.second].PB(e.first);
	}
	for(auto e:b){
		bTr[e.first].PB(e.second);
		bTr[e.second].PB(e.first);
	}
	dfs(root,-1,true,b);
	cerr<<vi(par,par+n)<<endl;
	REP(i,n)if(aliveC[i]==0)
		IncState(i);
	int ans=0;
	while(!qv.empty()){
		int v=qv.front();qv.pop();
		cerr<<root<<" "<<v<<endl;
		ans++;
		SetReady(v,bPar[v]);
		aliveC[par[v]]--;
		if(aliveC[par[v]]==0)
			IncState(par[v]);
	}
	if(done==n)
		return ans;
	else
		return inf;
}

void Solve(){
	int n=read();
	vector<pi> a=readTree(n),b=readTree(n);
	if(a==b)
		return print(0);
	int ans=inf;
	vi deg(n,0);
	for(auto e:a){
		deg[e.first]++;
		deg[e.second]++;
	}
	REP(i,n-1){
		REP(_,2){
			if(deg[a[i].first]==1){
				int tmp=a[i].second;
				REP(j,n)if(j!=a[i].first){
					a[i].second=j;
					chmin(ans,Sub(n,a[i].first,a,b));
				}
				a[i].second=tmp;
			}
			swap(a[i].first,a[i].second);
		}
	}
	if(ans<inf)
		print(ans+1);
	else
		print(-1);
}

signed main(){
	int t=read();
	REP(_,t)
		Solve();
}

### Prompt

Please create a solution in CPP 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 <bits/stdc++.h>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

vector<pi> readTree(int n){
	vector<pi> a;
	REP(i,n-1){
		int u=read()-1,v=read()-1;
		if(u>v)swap(u,v);
		a.PB(pi(u,v));
	}
	sort(ALL(a));
	return a;
}

bool findEdge(const vector<pi>& b,pi e){
	if(e.first>e.second)
		swap(e.first,e.second);
	auto itr=lower_bound(ALL(b),e);
	if(itr!=b.end()&&*itr==e)
		return true;
	else
		return false;
}

const int Nmax=55;
vi tr[Nmax],bTr[Nmax];
vi ch[Nmax];
int par[Nmax],bPar[Nmax],aliveC[Nmax],st[Nmax],done;
queue<int> qv;
void IncState(int v){
	st[v]++;
	if(st[v]==2)
		qv.push(v);
}
void SetReady(int v,int p){
	done++;
	st[v]=-inf;
	for(auto c:bTr[v])
		if(c!=p){
			IncState(c);
			bPar[c]=v;
		}
}
void dfs(int v,int p,bool fixed,const vector<pi>& b){
	par[v]=p;
	for(auto to:tr[v])
		if(to!=p){
			bool f=fixed&&findEdge(b,pi(v,to));
			ch[v].PB(to);
			aliveC[v]++;
			dfs(to,v,f,b);
		}
	if(fixed)
		SetReady(v,p);
}

int Sub(int n,int root,const vector<pi>& a,const vector<pi>& b){
	cerr<<a<<endl;
	REP(i,n){
		tr[i]=vi();
		bTr[i]=vi();
		ch[i]=vi();
		par[i]=-1;
		bPar[i]=-1;
		aliveC[i]=0;
		st[i]=0;
	}
	done=0;
	qv=queue<int>();
	for(auto e:a){
		tr[e.first].PB(e.second);
		tr[e.second].PB(e.first);
	}
	for(auto e:b){
		bTr[e.first].PB(e.second);
		bTr[e.second].PB(e.first);
	}
	dfs(root,-1,true,b);
	cerr<<vi(par,par+n)<<endl;
	REP(i,n)if(aliveC[i]==0)
		IncState(i);
	int ans=0;
	while(!qv.empty()){
		int v=qv.front();qv.pop();
		cerr<<root<<" "<<v<<endl;
		ans++;
		SetReady(v,bPar[v]);
		aliveC[par[v]]--;
		if(aliveC[par[v]]==0)
			IncState(par[v]);
	}
	if(done==n)
		return ans;
	else
		return inf;
}

void Solve(){
	int n=read();
	vector<pi> a=readTree(n),b=readTree(n);
	if(a==b)
		return print(0);
	int ans=inf;
	vi deg(n,0);
	for(auto e:a){
		deg[e.first]++;
		deg[e.second]++;
	}
	REP(i,n-1){
		REP(_,2){
			if(deg[a[i].first]==1){
				int tmp=a[i].second;
				REP(j,n)if(j!=a[i].first){
					a[i].second=j;
					chmin(ans,Sub(n,a[i].first,a,b));
				}
				a[i].second=tmp;
			}
			swap(a[i].first,a[i].second);
		}
	}
	if(ans<inf)
		print(ans+1);
	else
		print(-1);
}

signed main(){
	int t=read();
	REP(_,t)
		Solve();
}

```