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;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 50 + 5;

int test, n;

set<int> graph[N], gr[N], graph1[N], gr1[N];
int par[N], lvl[N], sum[N], used[N], ans;
set<int>::iterator it;
bool vis[N];
queue<int> q;

void bfs(int p) {
    q.push(p);
    lvl[p] = 0;
    used[p] = 1;
    memset(vis, 0, sizeof(vis));
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 1;
        for(it = graph1[u].begin(); it != graph1[u].end(); it++) {
            int v = *it;
            //cout << v << "\n";
            if(vis[v]) continue;
            vis[v] = 1;
            par[v] = u;
            lvl[v] = lvl[u] + 1;
            q.push(v);
        }
    }
}

int lmao() {
    int cnt = 0, amount = 0;
    for(int i = 1; i <= n; i++)
        sum[lvl[i]]++;
    while(1) {
        int ok = 0;
        for(int i = 1; i <= n; i++) {
            if(used[par[i]] && gr[i].find(par[i]) != gr[i].end() && !used[i]) {
                sum[lvl[i]]--;
                ok = 1;
                used[i] = 1;
            }
        }
        if(!ok)
            break;
    }
    while(1){
        int ok = 0;
        for(int i = 1; i <= n; i++) {
            if(!used[i] && gr[i].size() == 1 && used[par[i]]) {
                int u = *(gr[i].begin());
                gr[u].erase(i);
                gr[i].erase(u);
                gr[par[i]].insert(i);
                gr[i].insert(par[i]);
                ok = 1;
                amount++;
                used[i] = 1;
                sum[lvl[i]]--;
                break;
            }
        }
        if(!ok) break;
    }
    for(int i = 1; i <= n; i++) {
        if(sum[i])
            return -2;
    }
    return amount;
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    cin >> test;
    while(test--) {
        cin >> n;
        for(int i = 1; i <= n; i++)
            graph[i].clear(), gr[i].clear(), graph1[i].clear();
        ans = n + 1;
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].insert(v);
            graph[v].insert(u);
        }
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            graph1[u].insert(v);
            graph1[v].insert(u);
        }
        int ck = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++)
                sum[j] = 0, lvl[j] = 0, used[j] = 0;
            for(int j = 1; j <= n; j++)
                gr[j] = graph[j];
            bfs(i);
            int s = lmao();
            if(s >= 0)
                ans = min(ans, s);
        }
        for(int j = 1; j <= n; j++)
            gr1[j] = graph1[j];
        for(int i = 1; i <= n; i++) {
            if(graph[i].size() != 1) continue;
            for(int j = 1; j <= n; j++) {
                if(i == j) continue;
                for(int j = 1; j <= n; j++)
                    gr[j] = graph[j];
                for(int j = 1; j <= n; j++)
                    sum[j] = 0, lvl[j] = 0, used[j] = 0;
                if(gr[i].find(j) != gr[i].end()) continue;
                int u = *(gr[i].begin());
                gr[i].erase(u);
                gr[u].erase(i);
                gr[j].insert(i);
                gr[i].insert(j);
                bfs(i);
                int s = lmao() + 1;
                if(s >= 0)
                    ans = min(ans, s);
            }
        }
        if(ans == n + 1)
            cout << -1 << "\n";
        else
            cout << ans << "\n";
    }
}