#include<bits/stdc++.h>
#define Fail puts("NO"),exit(0);
#define eps 1e-10
#define maxn 55
#define maxm 100010
#define inf 1000000007
#define mod 1000000007
#define pi acos(-1)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef bitset<maxn> bit;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
int n;
int a[maxn][maxn],fa_a[maxn],fa_b[maxn],deg[maxn];
struct Graph{
    int head[maxn],nxt[maxn*2],to[maxn*2],tot;
    void add(int u,int v)
    {
        tot++;
        nxt[tot]=head[u];
        head[u]=tot;
        to[tot]=v;
    }
    void dfs(int x,int las,int *fa)
    {
        for(int i=head[x];i;i=nxt[i])
        {
            if(to[i]==las)  continue;
            fa[to[i]]=x;
            dfs(to[i],x,fa);
        }
    }
    void init()
    {
        memset(head,0,sizeof(head));tot=0;
    }
}A,B;
int book[maxn];
int degx[maxn];
int head[maxn],nxt[maxn*2],to[maxn*2],tot;
void add(int u,int v)
{
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
queue<int>q;
bool check()
{
    for(int i=1;i<=n;i++)
      if(!degx[i]&&book[i])  q.push(i);
    while(q.size())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=nxt[i])
        {
            degx[to[i]]--;
            if(!degx[to[i]])  q.push(to[i]);
        }
    }
    for(int i=1;i<=n;i++)
      if(book[i]&&degx[i])  return false;
    return true;
}
int solve(int rt,int x)
{
    memset(degx,0,sizeof(degx));
    tot=0;memset(head,0,sizeof(head));
    A.dfs(x,0,fa_a);fa_a[x]=rt;fa_a[rt]=0;
    B.dfs(rt,0,fa_b);fa_b[rt]=0;
    int res=0;
    for(int i=1;i<=n;i++)  book[i]=(fa_a[i]!=fa_b[i]),res+=book[i];
    for(int i=1;i<=n;i++)
    {
        if(i==rt)  continue;
        if(!book[i]&&book[fa_a[i]])  return inf;
        if(book[i]&&book[fa_a[i]])  add(i,fa_a[i]),degx[fa_a[i]]++;
        if(book[i]&&book[fa_b[i]])  add(fa_b[i],i),degx[i]++;
    }
    if(check())  return res;
    return inf;
}
int main()
{
    T=read();
    while(T--)
    {
        A.init();B.init();
        memset(a,0,sizeof(a));
        memset(deg,0,sizeof(deg));
        n=read();int ans=inf;
        for(int i=1;i<n;i++)
        {
            int x=read(),y=read();
            A.add(x,y);A.add(y,x);
            deg[x]++;deg[y]++;
            a[x][y]=a[y][x]=1;
        }
        for(int i=1;i<n;i++)
        {
            int x=read(),y=read();
            B.add(x,y);B.add(y,x);
        }
        for(int i=1;i<=n;i++)
        {
            if(deg[i]!=1)  continue;
            for(int j=1;j<=n;j++)
            {
                if(i==j)  continue;
                ans=min(ans,solve(i,j)+(!a[i][j]));
            }
        }
        if(ans==inf)  puts("-1");
        else          printf("%d\n",ans);
    }
    return 0;
}
### Prompt

Your challenge is to write a cpp solution 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>
#define Fail puts("NO"),exit(0);
#define eps 1e-10
#define maxn 55
#define maxm 100010
#define inf 1000000007
#define mod 1000000007
#define pi acos(-1)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef bitset<maxn> bit;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
int n;
int a[maxn][maxn],fa_a[maxn],fa_b[maxn],deg[maxn];
struct Graph{
    int head[maxn],nxt[maxn*2],to[maxn*2],tot;
    void add(int u,int v)
    {
        tot++;
        nxt[tot]=head[u];
        head[u]=tot;
        to[tot]=v;
    }
    void dfs(int x,int las,int *fa)
    {
        for(int i=head[x];i;i=nxt[i])
        {
            if(to[i]==las)  continue;
            fa[to[i]]=x;
            dfs(to[i],x,fa);
        }
    }
    void init()
    {
        memset(head,0,sizeof(head));tot=0;
    }
}A,B;
int book[maxn];
int degx[maxn];
int head[maxn],nxt[maxn*2],to[maxn*2],tot;
void add(int u,int v)
{
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
queue<int>q;
bool check()
{
    for(int i=1;i<=n;i++)
      if(!degx[i]&&book[i])  q.push(i);
    while(q.size())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=nxt[i])
        {
            degx[to[i]]--;
            if(!degx[to[i]])  q.push(to[i]);
        }
    }
    for(int i=1;i<=n;i++)
      if(book[i]&&degx[i])  return false;
    return true;
}
int solve(int rt,int x)
{
    memset(degx,0,sizeof(degx));
    tot=0;memset(head,0,sizeof(head));
    A.dfs(x,0,fa_a);fa_a[x]=rt;fa_a[rt]=0;
    B.dfs(rt,0,fa_b);fa_b[rt]=0;
    int res=0;
    for(int i=1;i<=n;i++)  book[i]=(fa_a[i]!=fa_b[i]),res+=book[i];
    for(int i=1;i<=n;i++)
    {
        if(i==rt)  continue;
        if(!book[i]&&book[fa_a[i]])  return inf;
        if(book[i]&&book[fa_a[i]])  add(i,fa_a[i]),degx[fa_a[i]]++;
        if(book[i]&&book[fa_b[i]])  add(fa_b[i],i),degx[i]++;
    }
    if(check())  return res;
    return inf;
}
int main()
{
    T=read();
    while(T--)
    {
        A.init();B.init();
        memset(a,0,sizeof(a));
        memset(deg,0,sizeof(deg));
        n=read();int ans=inf;
        for(int i=1;i<n;i++)
        {
            int x=read(),y=read();
            A.add(x,y);A.add(y,x);
            deg[x]++;deg[y]++;
            a[x][y]=a[y][x]=1;
        }
        for(int i=1;i<n;i++)
        {
            int x=read(),y=read();
            B.add(x,y);B.add(y,x);
        }
        for(int i=1;i<=n;i++)
        {
            if(deg[i]!=1)  continue;
            for(int j=1;j<=n;j++)
            {
                if(i==j)  continue;
                ans=min(ans,solve(i,j)+(!a[i][j]));
            }
        }
        if(ans==inf)  puts("-1");
        else          printf("%d\n",ans);
    }
    return 0;
}
```