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;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    vector<vector<int>> a(n), b(n);
    for (int i = 0; i < n - 1; ++i) {
      int x, y;
      scanf("%d %d", &x, &y);
      --x;
      --y;
      a[x].push_back(y);
      a[y].push_back(x);
    }
    for (int i = 0; i < n - 1; ++i) {
      int x, y;
      scanf("%d %d", &x, &y);
      --x;
      --y;
      b[x].push_back(y);
      b[y].push_back(x);
    }
    for (int i = 0; i < n; ++i) {
      sort(a[i].begin(), a[i].end());
      sort(b[i].begin(), b[i].end());
    }
    bool same = true;
    for (int i = 0; i < n; ++i) {
      if (a[i] != b[i]) {
        same = false;
        break;
      }
    }
    if (same) {
      puts("0");
    } else {
      int answer = n;
      int dfn_t = 0;

      vector<int> parent_a(n), parent_b(n), begin_a(n), begin_b(n), end_a(n), end_b(n);
      vector<bool> same(n);
      int dfn, result;

      function<void(int, int)> dfs_a = [&](int x, int p) {
        begin_a[x] = dfn++;
        parent_a[x] = p;
        for (auto y : a[x]) {
          if (y != p) {
            dfs_a(y, x);
          }
        }
        end_a[x] = dfn;
      };
      
      function<void(int, int)> dfs_b = [&](int x, int p) {
        begin_b[x] = dfn++;
        parent_b[x] = p;
        if (~p) {
          same[x] = parent_a[x] == parent_b[x] && same[p];
          if (same[x]) {
            ++result;
          }
        } else {
          same[x] = true;
          result = 1;
        }
        for (auto y : b[x]) {
          if (y != p) {
            dfs_b(y, x);
          }
        }
        end_b[x] = dfn;
      };

      auto solve = [&](int p) {
        dfn = 0;
        dfs_a(p, -1);
        dfn = 0;
        dfs_b(p, -1);
        vector<vector<int>> adj(n);
        vector<int> degree(n);
        for (int i = 0; i < n; ++i) {
          if (i != p && !same[i] && !same[parent_a[i]]) {
            adj[i].push_back(parent_a[i]);
            ++degree[parent_a[i]];
          }
        }
        for (int i = 0; i < n; ++i) {
          if (i != p && !same[i] && !same[parent_b[i]]) {
            adj[parent_b[i]].push_back(i);
            ++degree[i];
          }
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
          if (!degree[i]) {
            q.push(i);
          }
        }
        while (!q.empty()) {
          int x = q.front();
          q.pop();
          for (auto y : adj[x]) {
            if (!--degree[y]) {
              q.push(y);
            }
          }
        }
        for (int i = 0; i < n; ++i) {
          if (degree[i]) {
            return;
          }
        }
        answer = min(answer, n - result);
      };

      for (int i = 0; i < n; ++i) {
        if (b[i].size() == 1) {
          int p = b[i][0];
          for (int j = 0; j < b[p].size(); ++j) {
            if (b[p][j] == i) {
              swap(b[p][j], b[p][b[p].size() - 1]);
              break;
            }
          }
          for (int j = 0; j < n; ++j) {
            b[i].pop_back();
            b[p].pop_back();
            b[i].push_back(j);
            b[j].push_back(i);
            solve(i);
            b[i].pop_back();
            b[j].pop_back();
            b[i].push_back(p);
            b[p].push_back(i);
          }
        }
      } 
      if (answer == n) {
        puts("-1");
      } else {
        printf("%d\n", answer + 1);
      }
    }
  }
  return 0;
}