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 <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int Q=1<<8;
struct graph{
    int las[Q],e[Q],nn[Q],inc;
    void ins(int x,int y)
    {
        e[++inc]=y;
        nn[inc]=las[x];
        las[x]=inc;
    }
}t1,t2,g;
int ap[Q][Q];
queue<int> q;
int lv[Q];
int Time=0;
int H;
void dfs(int x,int last,graph b,int ty)
{
    if(max(lv[x],lv[last])<Time)
        g.ins(ty?x:last,ty?last:x);
    for(int t=b.las[x];t;t=b.nn[t]){
        int y=b.e[t];
        if(y==last)continue;
        dfs(y,x,b,ty);
    }
}
int vis[Q],huan;
void dfs(int x)
{
    if(huan)return;
    lv[x]=Time;
    vis[x]=1;
    for(int t=g.las[x];t&&(!huan);t=g.nn[t]){
        int y=g.e[t];
        if(lv[y]!=Time)dfs(y);
        else if(vis[y]){
            huan=1;
            return;
        }
    }
    vis[x]=0;
}
int n;
int Huan()
{
    huan=0;
    for(int j=1;j<=n;j++)
        vis[j]=0;
    ++Time;
    for(int j=1;j<=n&&(!huan);j++)if(lv[j]!=Time)dfs(j);
    return huan;
}
int Gans(int i)
{
    int als=998244353;
    q.push(i);
    lv[i]=++Time;
    int opha=0;
    while(q.size()){
        ++opha;
        int x=q.front();
        q.pop();
        for(int t=t1.las[x];t;t=t1.nn[t]){
            int y=t1.e[t];
            if(lv[y]==Time)continue;
            if(ap[x][y])
                lv[y]=Time,q.push(y);
        }
    }
    g.inc=0;
    for(int j=1;j<=n;j++)
        g.las[j]=0;
    dfs(i,0,t1,0);
    dfs(i,0,t2,1);
    return Huan()?998244353:(n-opha);
}
int d[Q];
int X1[Q],X2[Q],Y1[Q],Y2[Q];
int L[Q];
#define INS(p,a,b) (p.ins(a,b),p.ins(b,a))
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        t1.las[i]=t2.las[i]=0,d[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ap[i][j]=0;
    t1.inc=t2.inc=0;
    for(int i=1,x,y;i<n;i++)
        scanf("%d%d",&x,&y),INS(t1,x,y),++d[x],++d[y],X1[i]=x,Y1[i]=y,L[x]=L[y]=i;
    for(int i=1,x,y;i<n;i++)
        scanf("%d%d",&x,&y),INS(t2,x,y),ap[x][y]=ap[y][x]=1,X2[i]=x,Y2[i]=y;
    int als=998244353;
    for(int i=1;i<=n;i++)als=min(als,Gans(i));
    if(als>n)
    for(int i=1;i<=n;i++){
        if(d[i]!=1)continue;
        int id=L[i];
        for(int k=1;k<=n;k++){
            if(k==i)continue;
            for(int j=1;j<=n;j++)
                t1.las[j]=0;
            t1.inc=0;
            for(int j=1;j<n;j++){
                if(j!=id)INS(t1,X1[j],Y1[j]);
                else INS(t1,k,i);
            }
            if(Gans(i)<=n)
            {als=n;break;}
        }
    }
    printf("%d\n",als>n?-1:als);
}
int main()
{
    int t;
    for(scanf("%d",&t);t;--t)
        solve();
    return 0;
}