#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;


template<class T> ostream& operator<<(ostream& os, const V<T> &v) {
    cout << "[";
    for (auto p: v) cout << p << ", ";
    cout << "]";
    return os;
}

struct Solver {
    int n;
    VV<int> src, trg;
    V<int> s_par, t_par;
    void dfs(const VV<int> &g, V<int> &par, int p, int b) {
        par[p] = b;
        for (int d: g[p]) {
            if (d == b) continue;
            dfs(g, par, d, p);
        }
    }
    int check(int r) {
        s_par = V<int>(n);
        t_par = V<int>(n);
        dfs(src, s_par, r, -1);
        dfs(trg, t_par, r, -1);
        V<int> nch(n);
        for (int d: s_par) {
            if (d != -1) nch[d]++;
        }
        //cout << "SPAR: " << s_par << endl;
        //cout << "TPAR: " << t_par << endl;
        int cnt = 0;
        V<bool> ok(n);
        ok[r] = true;
        while (true) {
            bool update = false;
            for (int p = 0; p < n; p++) {
                if (ok[p]) continue;
                if (s_par[p] != t_par[p]) continue;
                if (!ok[s_par[p]]) continue;
                update = true;
                ok[p] = true;
            }
            if (update) continue;
            for (int p = 0; p < n; p++) {
                if (ok[p]) continue;
                if (nch[p]) continue;
                if (!ok[t_par[p]]) continue;
                cnt++;
                update = true;
                nch[s_par[p]]--;
                ok[p] = true;
                break;
            }
            if (update) continue;

            break;
        }
        for (int p = 0; p < n; p++) {
            if (!ok[p]) return TEN(9);
        }
        return cnt;
    }
    int solve() {
        int ans = TEN(9);
        cin >> n;
        VV<int> _src(n);
        trg = VV<int>(n);
        for (int i = 0; i < n-1; i++) {
            int a, b;
            cin >> a >> b; a--; b--;
            _src[a].push_back(b);
            _src[b].push_back(a);
        }
        for (int i = 0; i < n-1; i++) {
            int a, b;
            cin >> a >> b; a--; b--;
            trg[a].push_back(b);
            trg[b].push_back(a);
        }
        {
            bool same = true;
            for (int p = 0; p < n; p++) {
                set<int> s1(_src[p].begin(), _src[p].end());
                set<int> s2(trg[p].begin(), trg[p].end());
                if (s1 != s2) same = false;
            }
            if (same) return 0;
        }
        for (int p = 0; p < n; p++) {
            if (_src[p].size() != 1) continue;
            int px = _src[p][0];
            for (int q = 0; q < n; q++) {
                if (p == q) continue;
                //if (p != 0 || q != 1) continue;
                src = _src;
                src[p].clear();
                src[px].erase(
                        remove_if(src[px].begin(), src[px].end(), [&](int x){ return x == p; }),
                        src[px].end());
                src[p].push_back(q);
                src[q].push_back(p);
                int z = check(p);
                ans = min(ans, z + 1);
            }
        }
        return ans;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;
    int t;
    cin >> t;
    for (int ph = 0; ph < t; ph++) {
        Solver s;
        int ans = s.solve();
        if (ans > TEN(8)) ans = -1;
        cout << ans << endl;
    }
    return 0;
}

### Prompt

Create a solution in cpp for 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>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;


template<class T> ostream& operator<<(ostream& os, const V<T> &v) {
    cout << "[";
    for (auto p: v) cout << p << ", ";
    cout << "]";
    return os;
}

struct Solver {
    int n;
    VV<int> src, trg;
    V<int> s_par, t_par;
    void dfs(const VV<int> &g, V<int> &par, int p, int b) {
        par[p] = b;
        for (int d: g[p]) {
            if (d == b) continue;
            dfs(g, par, d, p);
        }
    }
    int check(int r) {
        s_par = V<int>(n);
        t_par = V<int>(n);
        dfs(src, s_par, r, -1);
        dfs(trg, t_par, r, -1);
        V<int> nch(n);
        for (int d: s_par) {
            if (d != -1) nch[d]++;
        }
        //cout << "SPAR: " << s_par << endl;
        //cout << "TPAR: " << t_par << endl;
        int cnt = 0;
        V<bool> ok(n);
        ok[r] = true;
        while (true) {
            bool update = false;
            for (int p = 0; p < n; p++) {
                if (ok[p]) continue;
                if (s_par[p] != t_par[p]) continue;
                if (!ok[s_par[p]]) continue;
                update = true;
                ok[p] = true;
            }
            if (update) continue;
            for (int p = 0; p < n; p++) {
                if (ok[p]) continue;
                if (nch[p]) continue;
                if (!ok[t_par[p]]) continue;
                cnt++;
                update = true;
                nch[s_par[p]]--;
                ok[p] = true;
                break;
            }
            if (update) continue;

            break;
        }
        for (int p = 0; p < n; p++) {
            if (!ok[p]) return TEN(9);
        }
        return cnt;
    }
    int solve() {
        int ans = TEN(9);
        cin >> n;
        VV<int> _src(n);
        trg = VV<int>(n);
        for (int i = 0; i < n-1; i++) {
            int a, b;
            cin >> a >> b; a--; b--;
            _src[a].push_back(b);
            _src[b].push_back(a);
        }
        for (int i = 0; i < n-1; i++) {
            int a, b;
            cin >> a >> b; a--; b--;
            trg[a].push_back(b);
            trg[b].push_back(a);
        }
        {
            bool same = true;
            for (int p = 0; p < n; p++) {
                set<int> s1(_src[p].begin(), _src[p].end());
                set<int> s2(trg[p].begin(), trg[p].end());
                if (s1 != s2) same = false;
            }
            if (same) return 0;
        }
        for (int p = 0; p < n; p++) {
            if (_src[p].size() != 1) continue;
            int px = _src[p][0];
            for (int q = 0; q < n; q++) {
                if (p == q) continue;
                //if (p != 0 || q != 1) continue;
                src = _src;
                src[p].clear();
                src[px].erase(
                        remove_if(src[px].begin(), src[px].end(), [&](int x){ return x == p; }),
                        src[px].end());
                src[p].push_back(q);
                src[q].push_back(p);
                int z = check(p);
                ans = min(ans, z + 1);
            }
        }
        return ans;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;
    int t;
    cin >> t;
    for (int ph = 0; ph < t; ph++) {
        Solver s;
        int ans = s.solve();
        if (ans > TEN(8)) ans = -1;
        cout << ans << endl;
    }
    return 0;
}

```