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 <iostream>
#include <vector>

using namespace std;

class Digraph {
  int n;
  vector<vector<int>> adj;

  void dfs (int u, vector<int> &vis, bool &ok) {
    vis[u] = 1;
    for (int nxt : adj[u]) {
      if (vis[nxt] == 0) {
        dfs(nxt, vis, ok);
      } else if (vis[nxt] == 1) {
        ok = false;
      }
    }
    vis[u] = 2;
  }
  
public:
  Digraph (int _n) : n(_n), adj(_n, vector<int> (0)) {}

  void add_edge (int u, int v) {
    adj[u].push_back(v);
  }

  bool dag () {
    vector<int> vis (n, 0);
    for (int i = 0; i < n; i++) {
      if (vis[i] == 0) {
        bool ok = true;
        dfs(i, vis, ok);
        if (!ok) return false;
      }
    }
    return true;
  }
};

const int MAX_N = 55;

int conn_a [MAX_N][MAX_N];
vector<int> adj_a [MAX_N];
vector<int> adj_b [MAX_N];

int safe [MAX_N];
void find_safes (int u, int p) {
  safe[u] = 1;
  for (int nxt : adj_b[u]) {
    if (nxt != p) {
      if (conn_a[u][nxt]) {
        find_safes(nxt, u);
      }
    }
  }
}

void fill_graph_a (int u, int p, Digraph &G) {
  for (int nxt : adj_a[u]) {
    if (nxt != p) {
      if (!safe[u]) {
        G.add_edge(u, nxt);
      }
      fill_graph_a(nxt, u, G);
    }
  }
}

void fill_graph_b (int u, int p, Digraph &G) {
  for (int nxt : adj_b[u]) {
    if (nxt != p) {
      if (!safe[u]) {
        G.add_edge(nxt, u);
      }
      fill_graph_b(nxt, u, G);
    }
  }
}

int try_root (int root, int n) {
  for (int i = 0; i < n; i++) {
    safe[i] = 0;
  }
  find_safes(root, -1);

  Digraph G (n);
  fill_graph_a(root, -1, G);
  fill_graph_b(root, -1, G);

  if (G.dag()) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
      if (!safe[i]) {
        ans++;
      }
    }
    return ans;
  } else {
    return MAX_N;
  }
}

int try_roots (int root_a, int root_b, int n) {
  for (int i = 0; i < n; i++) {
    safe[i] = 0;
  }

  Digraph G (n);
  fill_graph_a(root_a, -1, G);
  fill_graph_b(root_b, -1, G);

  if (G.dag()) {
    return n;
  } else {
    return MAX_N;
  }
}

void solve () {
  for (int i = 0; i < MAX_N; i++) {
    adj_a[i].clear();
    adj_b[i].clear();
    for (int j = 0; j < MAX_N; j++) {
      conn_a[i][j] = 0;
    }
  }
  
  int n;
  cin >> n;
  
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;

    conn_a[u][v] = 1;
    conn_a[v][u] = 1;
    adj_a[u].push_back(v);
    adj_a[v].push_back(u);
  }

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;

    adj_b[u].push_back(v);
    adj_b[v].push_back(u);
  }

  int ans = MAX_N;
  for (int i = 0; i < n; i++) {
    ans = min(ans, try_root(i, n));
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        ans = min(ans, try_roots(i, j, n));
      }
    }
  }
  
  if (ans == MAX_N) {
    cout << -1 << '\n';
  } else {
    cout << ans << '\n';
  }
}

int main () {
  ios::sync_with_stdio(false);

  int testc;
  cin >> testc;

  for (int i = 0; i < testc; i++) {
    solve();
  }
}