#include <bits/stdc++.h>

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector<vector<int>> g;
  int n;

  graph(int _n) : n(_n) {
    g.resize(n);
  }

  virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class digraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  digraph(int _n) : graph<T>(_n) {
  }

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }

  digraph<T> reverse() const {
    digraph<T> rev(n);
    for (auto &e : edges) {
      rev.add(e.to, e.from, e.cost);
    }
    return rev;
  }
};

template <typename T>
vector<int> find_scc(const digraph<T> &g, int &cnt) {
  digraph<T> g_rev = g.reverse();
  vector<int> order;
  vector<bool> was(g.n, false);
  function<void(int)> dfs1 = [&](int v) {
    was[v] = true;
    for (int id : g.g[v]) {
      auto &e = g.edges[id];
      int to = e.to;
      if (!was[to]) {
        dfs1(to);
      }
    }
    order.push_back(v);
  };
  for (int i = 0; i < g.n; i++) {
    if (!was[i]) {
      dfs1(i);
    }
  }
  vector<int> c(g.n, -1);
  function<void(int)> dfs2 = [&](int v) {
    for (int id : g_rev.g[v]) {
      auto &e = g_rev.edges[id];
      int to = e.to;
      if (c[to] == -1) {
        c[to] = c[v];
        dfs2(to);
      }
    }
  };
  cnt = 0;
  for (int id = g.n - 1; id >= 0; id--) {
    int i = order[id];
    if (c[i] != -1) {
      continue;
    }
    c[i] = cnt++;
    dfs2(i);
  }
  return c;
  // c[i] <= c[j] for every edge i -> j
}

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

template <typename T>
void debug_out(T t) {
  cerr << t;
}

template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}

template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << ", ";
  }
}

template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << endl;
  }
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" << endl, debug_out(__VA_ARGS__), cerr << endl;


int tt;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> tt;
  vector<int> ans;
  while(tt--) {
    int n;
    cin >> n;
    vector<vector<int>> to(n);
    vector<vector<int>> from(n);
    set<pair<int, int>> edges;
    dsu cur(n);
    range(i, 0, n - 1) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      from[u].push_back(v);
      from[v].push_back(u);
      edges.insert(make_pair(u, v));
      edges.insert(make_pair(v, u));
    }
    range(i, 0, n - 1) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      to[u].push_back(v);
      to[v].push_back(u);
      if(edges.find(make_pair(u, v)) != edges.end()) cur.unite(u, v);
    }
    int res = -1;
    vector<int> bar(n);
    range(i, 0, n) bar[cur.get(i)]++;
    range(i, 0, n) {
      digraph<int> st(n);
      function<void(int, int, bool)> dfs = [&](int v, int p, bool rev) {
        if(rev) {
          if(p != -1 && cur.get(v) != cur.get(i) && cur.get(p) != cur.get(i)) st.add(v, p);
          for(int u : from[v]) if(u != p) dfs(u, v, rev);
        } else {
          if(p != -1 && cur.get(v) != cur.get(i) && cur.get(p) != cur.get(i)) st.add(p, v);
          for(int u : to[v]) if(u != p) dfs(u, v, rev);
        }
      };
      dfs(i, -1, true);
      dfs(i, -1, false);
      int cnt = 0;
      find_scc(st, cnt);
      if(cnt == n) {
        res = max(res, bar[cur.get(i)]);
      }
    }
    if(res == -1) {
      if(true) {
        range(i, 0, n) {
          range(j, 0, n) {
            if(i == j) continue;
            digraph<int> st(n);
            function<void(int, int, bool)> dfs = [&](int v, int p, bool rev) {
              if(rev) {
                if(p != -1) st.add(v, p);
                for(int u : from[v]) if(u != p) dfs(u, v, rev);
              } else {
                if(p != -1) st.add(p, v);
                for(int u : to[v]) if(u != p) dfs(u, v, rev);
              }
            };
            dfs(i, -1, false);
            dfs(j, -1, true);
            int cnt = 0;
            find_scc(st, cnt);
            if(cnt == n) {
              res = 0;
              break;
            }
          }
          if(res == 0) break;
        }
      }
    }
    if(res != -1) res = n - res;
    cout << res << endl;
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector<vector<int>> g;
  int n;

  graph(int _n) : n(_n) {
    g.resize(n);
  }

  virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class digraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  digraph(int _n) : graph<T>(_n) {
  }

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }

  digraph<T> reverse() const {
    digraph<T> rev(n);
    for (auto &e : edges) {
      rev.add(e.to, e.from, e.cost);
    }
    return rev;
  }
};

template <typename T>
vector<int> find_scc(const digraph<T> &g, int &cnt) {
  digraph<T> g_rev = g.reverse();
  vector<int> order;
  vector<bool> was(g.n, false);
  function<void(int)> dfs1 = [&](int v) {
    was[v] = true;
    for (int id : g.g[v]) {
      auto &e = g.edges[id];
      int to = e.to;
      if (!was[to]) {
        dfs1(to);
      }
    }
    order.push_back(v);
  };
  for (int i = 0; i < g.n; i++) {
    if (!was[i]) {
      dfs1(i);
    }
  }
  vector<int> c(g.n, -1);
  function<void(int)> dfs2 = [&](int v) {
    for (int id : g_rev.g[v]) {
      auto &e = g_rev.edges[id];
      int to = e.to;
      if (c[to] == -1) {
        c[to] = c[v];
        dfs2(to);
      }
    }
  };
  cnt = 0;
  for (int id = g.n - 1; id >= 0; id--) {
    int i = order[id];
    if (c[i] != -1) {
      continue;
    }
    c[i] = cnt++;
    dfs2(i);
  }
  return c;
  // c[i] <= c[j] for every edge i -> j
}

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

template <typename T>
void debug_out(T t) {
  cerr << t;
}

template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}

template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << ", ";
  }
}

template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << endl;
  }
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" << endl, debug_out(__VA_ARGS__), cerr << endl;


int tt;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> tt;
  vector<int> ans;
  while(tt--) {
    int n;
    cin >> n;
    vector<vector<int>> to(n);
    vector<vector<int>> from(n);
    set<pair<int, int>> edges;
    dsu cur(n);
    range(i, 0, n - 1) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      from[u].push_back(v);
      from[v].push_back(u);
      edges.insert(make_pair(u, v));
      edges.insert(make_pair(v, u));
    }
    range(i, 0, n - 1) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      to[u].push_back(v);
      to[v].push_back(u);
      if(edges.find(make_pair(u, v)) != edges.end()) cur.unite(u, v);
    }
    int res = -1;
    vector<int> bar(n);
    range(i, 0, n) bar[cur.get(i)]++;
    range(i, 0, n) {
      digraph<int> st(n);
      function<void(int, int, bool)> dfs = [&](int v, int p, bool rev) {
        if(rev) {
          if(p != -1 && cur.get(v) != cur.get(i) && cur.get(p) != cur.get(i)) st.add(v, p);
          for(int u : from[v]) if(u != p) dfs(u, v, rev);
        } else {
          if(p != -1 && cur.get(v) != cur.get(i) && cur.get(p) != cur.get(i)) st.add(p, v);
          for(int u : to[v]) if(u != p) dfs(u, v, rev);
        }
      };
      dfs(i, -1, true);
      dfs(i, -1, false);
      int cnt = 0;
      find_scc(st, cnt);
      if(cnt == n) {
        res = max(res, bar[cur.get(i)]);
      }
    }
    if(res == -1) {
      if(true) {
        range(i, 0, n) {
          range(j, 0, n) {
            if(i == j) continue;
            digraph<int> st(n);
            function<void(int, int, bool)> dfs = [&](int v, int p, bool rev) {
              if(rev) {
                if(p != -1) st.add(v, p);
                for(int u : from[v]) if(u != p) dfs(u, v, rev);
              } else {
                if(p != -1) st.add(p, v);
                for(int u : to[v]) if(u != p) dfs(u, v, rev);
              }
            };
            dfs(i, -1, false);
            dfs(j, -1, true);
            int cnt = 0;
            find_scc(st, cnt);
            if(cnt == n) {
              res = 0;
              break;
            }
          }
          if(res == 0) break;
        }
      }
    }
    if(res != -1) res = n - res;
    cout << res << endl;
  }
  return 0;
}

```