#include<cstdio>
#define M 111
#define N 51
inline int min(int x,int y){return x<y?x:y;}
int A[N],B[M],C[M],F[N],Q[N],a[N],b[M],c[M],f[N],g[M],l,n,o[N],p[M],q[N],r,s,t;bool d[N],e[N],h[N];
bool check(int u)
{
    d[u]=e[u]=true;
    for(int i=o[u];i;i=p[i])
    if(!d[g[i]])
    if(!check(g[i]))return e[u]=false;
    else;
    else if(e[g[i]])return e[u]=false;
    return e[u]=false,true;
}
int i,u,v;
inline int get()
{
    for(i=1;i<=n;i++)d[i]=o[i]=0;
    for(f[q[l=0]=s]=0,r=1;l<r;)for(i=a[u=q[l++]];i;i=b[i])if(c[i]!=f[u]&&c[i]!=s)f[q[r++]=c[i]]=u;
    for(F[Q[l=0]=s]=0,r=1;l<r;)for(i=A[u=Q[l++]];i;i=B[i])if(C[i]!=F[u])F[Q[r++]=C[i]]=u;
    for(i=1,*h=true,r=0;i<=n;i++)h[i]=f[i]==F[i],r+=!h[i];
    for(i=1;i<=n;i++)if(h[i]&&!h[f[i]])return n+1;
    for(i=1,l=0;i<=n;i++)if(!h[i]&&!h[f[i]])p[++l]=o[i],g[o[i]=l]=f[i];
    for(i=1;i<=n;i++)if(!h[i]&&!h[F[i]])p[++l]=o[F[i]],g[o[F[i]]=l]=i;
    for(i=1;i<=n;i++)if(!d[i]&&!check(i))return n+1;
    return r;
}
int j,x,y;
inline void solve()
{
    for(scanf("%d",&n),i=1,x=n+1;i<n;i++)scanf("%d%d",&u,&v),b[i<<1]=a[u],c[a[u]=i<<1]=v,b[i<<1|1]=a[v],c[a[v]=i<<1|1]=u;
    for(i=1;i<n;i++)scanf("%d%d",&u,&v),B[i<<1]=A[u],C[A[u]=i<<1]=v,B[i<<1|1]=A[v],C[A[v]=i<<1|1]=u;
    for(s=1,j=0;s<=n;s++)x=min(x,get());
    for(s=1;s<=n;s++)if(!b[a[s]])
    {
        for(y=c[a[s]],j=1;j<=n;j++)if(j!=y)c[a[s]]=j,x=min(x,get()+1);
        c[a[s]]=y;
    }
    for(printf("%d\n",x==n+1?-1:x),i=1;i<=n;a[i]=A[i]=0,i++);
}
int main()
{
    for(scanf("%d",&t);t--;solve());
    return 0;
}
### Prompt

In cpp, your task is to solve 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<cstdio>
#define M 111
#define N 51
inline int min(int x,int y){return x<y?x:y;}
int A[N],B[M],C[M],F[N],Q[N],a[N],b[M],c[M],f[N],g[M],l,n,o[N],p[M],q[N],r,s,t;bool d[N],e[N],h[N];
bool check(int u)
{
    d[u]=e[u]=true;
    for(int i=o[u];i;i=p[i])
    if(!d[g[i]])
    if(!check(g[i]))return e[u]=false;
    else;
    else if(e[g[i]])return e[u]=false;
    return e[u]=false,true;
}
int i,u,v;
inline int get()
{
    for(i=1;i<=n;i++)d[i]=o[i]=0;
    for(f[q[l=0]=s]=0,r=1;l<r;)for(i=a[u=q[l++]];i;i=b[i])if(c[i]!=f[u]&&c[i]!=s)f[q[r++]=c[i]]=u;
    for(F[Q[l=0]=s]=0,r=1;l<r;)for(i=A[u=Q[l++]];i;i=B[i])if(C[i]!=F[u])F[Q[r++]=C[i]]=u;
    for(i=1,*h=true,r=0;i<=n;i++)h[i]=f[i]==F[i],r+=!h[i];
    for(i=1;i<=n;i++)if(h[i]&&!h[f[i]])return n+1;
    for(i=1,l=0;i<=n;i++)if(!h[i]&&!h[f[i]])p[++l]=o[i],g[o[i]=l]=f[i];
    for(i=1;i<=n;i++)if(!h[i]&&!h[F[i]])p[++l]=o[F[i]],g[o[F[i]]=l]=i;
    for(i=1;i<=n;i++)if(!d[i]&&!check(i))return n+1;
    return r;
}
int j,x,y;
inline void solve()
{
    for(scanf("%d",&n),i=1,x=n+1;i<n;i++)scanf("%d%d",&u,&v),b[i<<1]=a[u],c[a[u]=i<<1]=v,b[i<<1|1]=a[v],c[a[v]=i<<1|1]=u;
    for(i=1;i<n;i++)scanf("%d%d",&u,&v),B[i<<1]=A[u],C[A[u]=i<<1]=v,B[i<<1|1]=A[v],C[A[v]=i<<1|1]=u;
    for(s=1,j=0;s<=n;s++)x=min(x,get());
    for(s=1;s<=n;s++)if(!b[a[s]])
    {
        for(y=c[a[s]],j=1;j<=n;j++)if(j!=y)c[a[s]]=j,x=min(x,get()+1);
        c[a[s]]=y;
    }
    for(printf("%d\n",x==n+1?-1:x),i=1;i<=n;a[i]=A[i]=0,i++);
}
int main()
{
    for(scanf("%d",&t);t--;solve());
    return 0;
}
```