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<iostream>
#include<vector>
using namespace std;
const int N=53;
vector<int> adj[N],adj1[N],adj2[N];
bool check[N][N],check1[N][N],used[N],good[N];
int n,par[N],par1[N],used1[N];
void dfs(int x,int p){
  par[x]=p;
  for(int i=0;i<adj[x].size();i++){
    if(adj[x][i]!=p){
      if(good[x]&&check1[x][adj[x][i]]){
        good[adj[x][i]]=true;
      }
      dfs(adj[x][i],x);
    }
  }
}
void dfs1(int x,int p){
  par1[x]=p;
  for(int i=0;i<adj1[x].size();i++){
    if(adj1[x][i]!=p){
      dfs1(adj1[x][i],x);
    }
  }
}
bool dfs2(int x){
  for(int i=0;i<adj2[x].size();i++){
    if(used1[adj2[x][i]]==1){
      return false;
    }
    else{
      if(!used1[adj2[x][i]]){
      	used1[adj2[x][i]]=1;
      	if(!dfs2(adj2[x][i])){
          return false;
        }
        used1[adj2[x][i]]=2;
      }
    }
  }
  return true;
}
void dfs3(int x,int p){
  par[x]=p;
  for(int i=0;i<adj[x].size();i++){
    if(!used[adj[x][i]]){
      used[adj[x][i]]=true;
      if(good[x]&&check1[x][adj[x][i]]){
        good[adj[x][i]]=true;
      }
      dfs3(adj[x][i],x);
    }
  }
}
bool checkk(){
  int i;
  for(i=1;i<=n;i++){
    used1[i]=0;
  }
  for(i=1;i<=n;i++){
    if(!used1[i]){
      used1[i]=1;
      if(!dfs2(i)){
        return false;
      }
      used1[i]=2;
    }
  }
  return true;
}
void solve(){
  int i,j,k,ans;
  bool cac;
  cin>>n;
  ans=n+1;
  for(i=1;i<=n;i++){
    adj[i].clear();
    adj1[i].clear();
    for(j=1;j<=n;j++){
      check[i][j]=false;
      check1[i][j]=false;
    }
  }
  for(i=1;i<n;i++){
    cin>>j>>k;
    adj[j].push_back(k);
    adj[k].push_back(j);
    check[j][k]=true;
    check[k][j]=true;
  }
  for(i=1;i<n;i++){
    cin>>j>>k;
    adj1[j].push_back(k);
    adj1[k].push_back(j);
    check1[j][k]=true;
    check1[k][j]=true;
  }
  for(i=1;i<=n;i++){
   	for(j=1;j<=n;j++){
      adj2[j].clear();
      good[j]=false;
    }
    good[i]=true;
    dfs(i,i);
    dfs1(i,i);
    cac=true;
    k=0;
    for(j=1;j<=n;j++){
      if(good[j]){
        k++;
      }
      if(par[j]==par1[j]){
        if(!good[j]){
          cac=false;
          break;
        }
      }
      else{
        if(!good[j]&&!good[par1[j]]){
        	adj2[par1[j]].push_back(j);
        }
        if(!good[j]&&!good[par[j]]){
        	adj2[j].push_back(par[j]);
        }
      }
    }
    if(cac&&checkk()){
      ans=min(ans,n-k);
    }
  }
  if(ans<n){
    cout<<ans<<'\n';
    return;
  }
  for(i=1;i<=n;i++){
    if(adj[i].size()!=1){
      continue;
    }
    for(j=1;j<=n;j++){
      if(j==i||j==adj[i][0]){
        continue;
      }
      for(k=1;k<=n;k++){
        adj2[k].clear();
        used[k]=false;
        good[k]=false;
      }
      used[i]=true;
      used[j]=true;
      good[i]=true;
      if(check1[i][j]){
        good[j]=true;
      }
      par[i]=i;
      dfs1(i,i);
      dfs3(j,i);
      cac=true;
      for(k=1;k<=n;k++){
        if(par[k]==par1[k]){
          if(!good[k]){
            cac=false;
            break;
          }
        }
        else{
          if(!good[par1[k]]&&!good[k]){
          	adj2[par1[k]].push_back(k);
          }
          if(!good[k]&&!good[par[k]]){
          	adj2[k].push_back(par[k]);
          }
        }
      }
      if(cac&&checkk()){
        cout<<n<<'\n';
        return;
      }
    }
  }
  cout<<"-1\n";
  return;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin>>t;
  while(t--){
    solve();
  }
  return 0;
}