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

Solution (in CPP):

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

const int N=100;
int ch[N],fA[N],fB[N],col[N],n,T;
vector<int>ga[N],gb[N];
queue<int>q;

void dfsA(int x){ch[x]=0;for(int i:ga[x])if(i!=fA[x])fA[i]=x,dfsA(i),++ch[x];}
void dfsB(int x,int y){col[x]=y;for(int i:gb[x])if(i!=fB[x])fB[i]=x,dfsB(i,y&&x==fA[i]);}

void ins(int t){for(int i:gb[t])if(!col[i]&&!ch[i])q.push(i);}
void clear(){
	for(int i=1;i<=n;++i)ga[i].clear(),gb[i].clear();
}
int work(int x){
	int u=ga[x][0];
	fA[x]=fB[x]=0;
	dfsA(x);dfsB(x,1);
	for(int i=1;i<=n;++i)if(col[i])ins(i);
	int cnt=0;
	for(;!q.empty();){
		int t=q.front();q.pop();++cnt;
		col[t]=1;ins(t);--ch[fA[t]];
		if(!ch[fA[t]]&&!col[fA[t]])for(int i:gb[fA[t]])if(col[i]){q.push(fA[t]);break;}
	}
	for(int i=1;i<=n;++i)if(!col[i])return n+1;
	return cnt;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(cin>>T;T--;){
		cin>>n;
		for(int i=1;i<n;++i){
			int x,y;cin>>x>>y;
			ga[x].push_back(y);ga[y].push_back(x);
		}
		for(int i=1;i<n;++i){
			int x,y;cin>>x>>y;
			gb[x].push_back(y);gb[y].push_back(x);
		}
		int flag=1;
		for(int i=1;i<=n;++i){
			sort(ga[i].begin(),ga[i].end());
			sort(gb[i].begin(),gb[i].end());
			if(ga[i]!=gb[i])flag=0;
		}
		if(flag){cout<<0<<'\n';clear();continue;}
		int ans=n+1;
		for(int i=1;i<=n;++i)if((int)ga[i].size()==1){
			int f=ga[i][0];ga[f].erase(lower_bound(ga[f].begin(),ga[f].end(),i));
			for(int j=1;j<=n;++j)if(j!=i&&j!=f){
				ga[i][0]=j;
				ga[j].insert(lower_bound(ga[j].begin(),ga[j].end(),i),i);
				ans=min(ans,work(i)+1);
				ga[j].erase(lower_bound(ga[j].begin(),ga[j].end(),i));
			}
			ga[i][0]=f;
			ga[f].insert(lower_bound(ga[f].begin(),ga[f].end(),i),i);
		}
		cout<<(ans==n+1?-1:ans)<<'\n';clear();
	}
	return 0;
}