#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=100;

int n;
int ga[N][N],gb[N][N];
int col[N],d[N];

vector<int> glim[N];
void add_lim(int x,int y){
    //printf("add_lim(%d,%d)\n",x,y);
    glim[x].pb(y);
    d[y]++;
}

void dfs(int u,int p){
    col[u]=1;//不动的点
    FOR(v,1,n)if(ga[u][v]&&gb[u][v]&&v!=p)dfs(v,u);
}
void dfsa(int u,int p){
    FOR(v,1,n)if(ga[u][v]&&v!=p){
        dfsa(v,u);
        if(!col[u]&&!col[v]){
            add_lim(v,u);
        }
    }
}
void dfsb(int u,int p){
    FOR(v,1,n)if(gb[u][v]&&v!=p){
        dfsb(v,u);
        if(!col[u]&&!col[v]){
            add_lim(u,v);
        }
    }
}
int vis[N],tim;
bool dfs_lim(int u){
    if(vis[u]==tim){
        //printf("u=%d\n",u);
        return 1;
    }
    vis[u]=tim;
    for(int v:glim[u])if(dfs_lim(v))return 1;
    return 0;
}
int get_ans(int r){
    //printf("get_ans(%d)\n",r);
    memset(col,0,sizeof(col));
    dfs(r,0);
    int res=0;
    FOR(i,1,n)res+=!col[i];
    FOR(i,1,n)glim[i].clear();
    memset(d,0,sizeof(d));
    dfsa(r,0);
    dfsb(r,0);
    queue<int> q;
    FOR(i,1,n)if(d[i]==0)q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:glim[u]){
            d[v]--;
            if(d[v]==0)q.push(v);
        }
    }
    FOR(i,1,n)if(d[i])return -1;
    return res;
}
void go(){
    scanf("%d",&n);
    memset(ga,0,sizeof(ga));
    memset(gb,0,sizeof(gb));
    FOR(i,1,n-1){ int a,b; scanf("%d%d",&a,&b); ga[a][b]=ga[b][a]=1; }
    FOR(i,1,n-1){ int a,b; scanf("%d%d",&a,&b); gb[a][b]=gb[b][a]=1; }
    int ans=0x3f3f3f3f;
    FOR(i,1,n){
        int t=get_ans(i);
        if(t!=-1)ans=min(ans,t);
    }
    FOR(i,1,n){
        int dg=0,p=0;
        FOR(j,1,n)if(ga[i][j])p=j,++dg;
        if(dg>1)continue;
        ga[i][p]=ga[p][i]=0;
        FOR(j,1,n){
            if(i==j)continue;
            ga[i][j]=ga[j][i]=1;
            int t=get_ans(i);
            if(t!=-1)ans=min(ans,t+1);
            ga[i][j]=ga[j][i]=0;
        }
        ga[i][p]=ga[p][i]=1;
    }
    printf("%d\n",ans==0x3f3f3f3f?-1:ans);
}
int main(){
    int t;
    scanf("%d",&t);
    FOR(i,1,t)go();
    return 0;
}

### Prompt

Please create a solution in cpp 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<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=100;

int n;
int ga[N][N],gb[N][N];
int col[N],d[N];

vector<int> glim[N];
void add_lim(int x,int y){
    //printf("add_lim(%d,%d)\n",x,y);
    glim[x].pb(y);
    d[y]++;
}

void dfs(int u,int p){
    col[u]=1;//不动的点
    FOR(v,1,n)if(ga[u][v]&&gb[u][v]&&v!=p)dfs(v,u);
}
void dfsa(int u,int p){
    FOR(v,1,n)if(ga[u][v]&&v!=p){
        dfsa(v,u);
        if(!col[u]&&!col[v]){
            add_lim(v,u);
        }
    }
}
void dfsb(int u,int p){
    FOR(v,1,n)if(gb[u][v]&&v!=p){
        dfsb(v,u);
        if(!col[u]&&!col[v]){
            add_lim(u,v);
        }
    }
}
int vis[N],tim;
bool dfs_lim(int u){
    if(vis[u]==tim){
        //printf("u=%d\n",u);
        return 1;
    }
    vis[u]=tim;
    for(int v:glim[u])if(dfs_lim(v))return 1;
    return 0;
}
int get_ans(int r){
    //printf("get_ans(%d)\n",r);
    memset(col,0,sizeof(col));
    dfs(r,0);
    int res=0;
    FOR(i,1,n)res+=!col[i];
    FOR(i,1,n)glim[i].clear();
    memset(d,0,sizeof(d));
    dfsa(r,0);
    dfsb(r,0);
    queue<int> q;
    FOR(i,1,n)if(d[i]==0)q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:glim[u]){
            d[v]--;
            if(d[v]==0)q.push(v);
        }
    }
    FOR(i,1,n)if(d[i])return -1;
    return res;
}
void go(){
    scanf("%d",&n);
    memset(ga,0,sizeof(ga));
    memset(gb,0,sizeof(gb));
    FOR(i,1,n-1){ int a,b; scanf("%d%d",&a,&b); ga[a][b]=ga[b][a]=1; }
    FOR(i,1,n-1){ int a,b; scanf("%d%d",&a,&b); gb[a][b]=gb[b][a]=1; }
    int ans=0x3f3f3f3f;
    FOR(i,1,n){
        int t=get_ans(i);
        if(t!=-1)ans=min(ans,t);
    }
    FOR(i,1,n){
        int dg=0,p=0;
        FOR(j,1,n)if(ga[i][j])p=j,++dg;
        if(dg>1)continue;
        ga[i][p]=ga[p][i]=0;
        FOR(j,1,n){
            if(i==j)continue;
            ga[i][j]=ga[j][i]=1;
            int t=get_ans(i);
            if(t!=-1)ans=min(ans,t+1);
            ga[i][j]=ga[j][i]=0;
        }
        ga[i][p]=ga[p][i]=1;
    }
    printf("%d\n",ans==0x3f3f3f3f?-1:ans);
}
int main(){
    int t;
    scanf("%d",&t);
    FOR(i,1,t)go();
    return 0;
}

```