//https://agc027.contest.atcoder.jp/tasks/agc027_f
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

using V = vector<int>;
using VV = vector<V>;
int N;

void tree(VV& g,VV &t,int v,int p){
    for(int u:g[v]){
        if(u==p)continue;
        t[v].push_back(u);
        tree(g,t,u,v);
    }
}
void malta(int v,VV &g,V &S){
    S[v]=1;
    for(int u:g[v]){
        malta(u,g,S);
    }
}
void dfs(int v,VV &a,VV &b,V&uA,V&uB,V&S,V&T){
    int i=0,j=0;
    int mi=a[v].size();
    int mj=b[v].size();
    while(i<mi||j<mj){
        if(i<mi&&(j==mj||a[v][i]<b[v][j])){
            malta(a[v][i],a,S);
            i++;
        }
        else if(i==mi||a[v][i]>b[v][j]){
            malta(b[v][j],b,T);
            uB[b[v][j]]=1;
            j++;
        }
        else {
            dfs(a[v][i],a,b,uA,uB,S,T);
            i++;j++;
        }
    }
}
int latte(int r,VV A,VV B){
    VV a(N),b(N);
    tree(A,a,r,r);
    tree(B,b,r,r);
    V uA(N,0),uB(N,0),S(N,0),T(N,0);
    dfs(r,a,b,uA,uB,S,T);
    if(S!=T)return 100;
    for(int v:range(N)){
        if(S[v]==1){
            uA[v]=1+a[v].size();
        }
    }
    V rA(N,-1);
    for(int v:range(N)){
        for(int u:a[v]){
            if(S[v]==1&&S[u]==1){
                rA[u]=v;
            }
        }
    }
    int ret = 0;
    for(int it:S)ret+=it;
    for(bool update=true;update;){
        update=false;
        for(int i:range(N)){
            if(uA[i]==1&&uB[i]==1){
                uA[i]--;
                if(rA[i]!=-1)uA[rA[i]]--;
                uB[i]--;
                for(int j:b[i])uB[j]++;
                update=true;
            }
        }
    }        

    if(*max_element(ALL(uB))==0)return ret;
    else return 100;
}
void solve(){
    cin>>N;
    VV A(N),B(N);
    for(int i:range(N-1)){
        int a,b;
        cin>>a>>b;a--;b--;
        A[a].push_back(b);
        A[b].push_back(a);
    }
    for(int i:range(N-1)){
        int a,b;
        cin>>a>>b;a--;b--;
        B[a].push_back(b);
        B[b].push_back(a);
    }
    for(int i:range(N)){
        sort(ALL(A[i]));
        sort(ALL(B[i]));
    }
    int ret= 100;
    for(int i:range(N)){
        chmin(ret,latte(i,A,B));
    }
    if(ret==100){
        for(int i:range(N)){
            if(A[i].size()==1){
                int k = A[i][0];
                for(int j:range(N)){
                    if(j==i)continue;
                    if(j==k)continue;
                    VV nA=A;
                    nA[i][0]=j;
                    for(int p:range(nA[k].size())){
                        if(nA[k][p]==i){
                            swap(nA[k][p],nA[k].back());
                            nA[k].pop_back();
                            break;
                        }
                    }
                    nA[j].push_back(i);
                    for(int p=nA[j].size()-1;p>0;p--){
                        if(nA[j][p]<nA[j][p-1])swap(nA[j][p],nA[j][p-1]);
                    }
                    chmin(ret,latte(i,nA,B)+1);
                }
            }
        }
    }
    if(ret==100)ret=-1;
    cout<<ret<<endl;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}

### 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
//https://agc027.contest.atcoder.jp/tasks/agc027_f
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

using V = vector<int>;
using VV = vector<V>;
int N;

void tree(VV& g,VV &t,int v,int p){
    for(int u:g[v]){
        if(u==p)continue;
        t[v].push_back(u);
        tree(g,t,u,v);
    }
}
void malta(int v,VV &g,V &S){
    S[v]=1;
    for(int u:g[v]){
        malta(u,g,S);
    }
}
void dfs(int v,VV &a,VV &b,V&uA,V&uB,V&S,V&T){
    int i=0,j=0;
    int mi=a[v].size();
    int mj=b[v].size();
    while(i<mi||j<mj){
        if(i<mi&&(j==mj||a[v][i]<b[v][j])){
            malta(a[v][i],a,S);
            i++;
        }
        else if(i==mi||a[v][i]>b[v][j]){
            malta(b[v][j],b,T);
            uB[b[v][j]]=1;
            j++;
        }
        else {
            dfs(a[v][i],a,b,uA,uB,S,T);
            i++;j++;
        }
    }
}
int latte(int r,VV A,VV B){
    VV a(N),b(N);
    tree(A,a,r,r);
    tree(B,b,r,r);
    V uA(N,0),uB(N,0),S(N,0),T(N,0);
    dfs(r,a,b,uA,uB,S,T);
    if(S!=T)return 100;
    for(int v:range(N)){
        if(S[v]==1){
            uA[v]=1+a[v].size();
        }
    }
    V rA(N,-1);
    for(int v:range(N)){
        for(int u:a[v]){
            if(S[v]==1&&S[u]==1){
                rA[u]=v;
            }
        }
    }
    int ret = 0;
    for(int it:S)ret+=it;
    for(bool update=true;update;){
        update=false;
        for(int i:range(N)){
            if(uA[i]==1&&uB[i]==1){
                uA[i]--;
                if(rA[i]!=-1)uA[rA[i]]--;
                uB[i]--;
                for(int j:b[i])uB[j]++;
                update=true;
            }
        }
    }        

    if(*max_element(ALL(uB))==0)return ret;
    else return 100;
}
void solve(){
    cin>>N;
    VV A(N),B(N);
    for(int i:range(N-1)){
        int a,b;
        cin>>a>>b;a--;b--;
        A[a].push_back(b);
        A[b].push_back(a);
    }
    for(int i:range(N-1)){
        int a,b;
        cin>>a>>b;a--;b--;
        B[a].push_back(b);
        B[b].push_back(a);
    }
    for(int i:range(N)){
        sort(ALL(A[i]));
        sort(ALL(B[i]));
    }
    int ret= 100;
    for(int i:range(N)){
        chmin(ret,latte(i,A,B));
    }
    if(ret==100){
        for(int i:range(N)){
            if(A[i].size()==1){
                int k = A[i][0];
                for(int j:range(N)){
                    if(j==i)continue;
                    if(j==k)continue;
                    VV nA=A;
                    nA[i][0]=j;
                    for(int p:range(nA[k].size())){
                        if(nA[k][p]==i){
                            swap(nA[k][p],nA[k].back());
                            nA[k].pop_back();
                            break;
                        }
                    }
                    nA[j].push_back(i);
                    for(int p=nA[j].size()-1;p>0;p--){
                        if(nA[j][p]<nA[j][p-1])swap(nA[j][p],nA[j][p-1]);
                    }
                    chmin(ret,latte(i,nA,B)+1);
                }
            }
        }
    }
    if(ret==100)ret=-1;
    cout<<ret<<endl;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}

```