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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct Tree {
    int n;
    vector<vector<int>> e;
    vector<vector<bool>> g;
    Tree(int n) : n(n), e(n), g(n, vector<bool>(n)) {}
    void addEdge(int u, int v) {
        e[u].push_back(v);
        e[v].push_back(u);
        g[u][v] = g[v][u] = true;
    }
    void removeEdge(int u, int v) {
        e[u].erase(find(e[u].begin(), e[u].end(), v));
        e[v].erase(find(e[v].begin(), e[v].end(), u));
        g[u][v] = g[v][u] = false;
    }
};
struct Graph {
    int n;
    vector<vector<int>> e;
    vector<int> in;
    Graph(int n) : n(n), e(n), in(n) {}
    void clear() {
        fill(in.begin(), in.end(), 0);
        for (int i = 0; i < n; ++i)
            e[i].clear();
    }
    void addEdge(int u, int v) {
        e[u].push_back(v);
        ++in[v];
    }
    bool isAcyclic() {
        queue<int> que;
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (in[i] == 0)
                que.push(i);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            ++cnt;
            for (int v : e[u]) {
                --in[v];
                if (in[v] == 0)
                    que.push(v);
            }
        }
        clear();
        return cnt == n;
    }
};
void solve() {
    int n;
    cin >> n;
    Tree a(n), b(n);
    Graph g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        a.addEdge(u, v);
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        b.addEdge(u, v);
    }
    auto solveFixed = [&](int r) {
        int ans = n;
        function<void(int, int, bool)> dfsa = [&](int u, int p, bool same) {
            if (same)
                --ans;
            for (int v : a.e[u]) {
                if (v == p)
                    continue;
                dfsa(v, u, same && b.g[u][v]);
                if (!same)
                    g.addEdge(v, u);
            }
        };
        function<void(int, int, bool)> dfsb = [&](int u, int p, bool same) {
            for (int v : b.e[u]) {
                if (v == p)
                    continue;
                dfsb(v, u, same && a.g[u][v]);
                if (!same)
                    g.addEdge(u, v);
            }
        };
        dfsa(r, -1, true);
        dfsb(r, -1, true);
        if (g.isAcyclic())
            return ans;
        return n + 1;
    };
    int ans = n + 1;
    for (int i = 0; i < n; ++i)
        ans = min(ans, solveFixed(i));
    for (int i = 0; i < n; ++i) {
        if (a.e[i].size() >= 2)
            continue;
        int v = a.e[i][0];
        a.removeEdge(i, v);
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                a.addEdge(i, j);
                ans = min(ans, solveFixed(i) + 1);
                a.removeEdge(i, j);
            }
        }
        a.addEdge(i, v);
    }
    cout << (ans > n ? -1 : ans) << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}