#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <queue>
#define FILL(a, n, x) memset((a), (x), sizeof ((a)[0]) * (n))
#define FILLA(a, x) memset((a), (x), sizeof (a))
#define COPY(a, n, b) memcpy((b), (a), sizeof ((a)[0]) * (n))
#define COPYA(a, b) memcpy((b), (a), sizeof (a))
using namespace std;

typedef pair<int, int> pii;
typedef long long li;
typedef unsigned long long lu;
const int inf = ~0U >> 2;
const li infl = ~0LLU >> 2;

template <class T> inline void Min(T &x, T y) { if (y < x) x = y; }
template <class T> inline void Max(T &x, T y) { if (y > x) x = y; }

// const int mod = 1e9 + 7;
// inline int Add(int x) { return x >= mod ? x - mod : x; }
// inline void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
// inline int Sub(int x) { return x < 0 ? x + mod : x; }
// inline void Sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
// inline int Mul(int x, int y) { return (int)((li)x * y % mod); }
// inline int Mul(int x, int y, int z) { return Mul(x, Mul(y, z)); }
// int Pow(int x, int y) { int z = 1;
//   for (; y; y >>= 1, x = Mul(x, x)) { if (y & 1) z = Mul(z, x); } return z; }
// inline int Inv(int x) { return Pow(x, mod - 2); }
// inline int Fix(li x) { x %= mod; if (x < 0) x += mod; return (int)x; }
// inline int Fix(int x) { x %= mod; if (x < 0) x += mod; return x; }

// ----------------------------------------

const int maxn = 50;

int n;
vector<int> A[maxn], B[maxn], C[maxn];
int par1[maxn], par2[maxn];

namespace part {
  vector<int> g[maxn];
  bool lock[maxn];
  int vis[maxn];
  bool cycle;

  void Dfs(int u) {
    if (vis[u] == 2) return;
    if (vis[u] == 1) {
      cycle = true;
      return;
    }
    vis[u] = 1;
    for (int v : g[u]) {
      Dfs(v);
      if (cycle) return;
    }
    vis[u] = 2;
  }

  bool Topo(void) {
    FILL(vis, n, 0);
    cycle = false;
    for (int i = 0; i < n; ++i) {
      Dfs(i);
      if (cycle) return false;
    }
    return true;
  }
  
  int Solve(int *par1, int *par2) {
    // should have the same root
    for (int i = 0; i < n; ++i) {
      g[i].clear();
    }
    for (int i = 0; i < n; ++i) {
      lock[i] = (par1[i] == par2[i]);
    }
    for (int i = 0; i < n; ++i) {
      if (par1[i] != -1 && lock[i] && !lock[par1[i]]) {
        return -1;
      }
      if (par2[i] != -1 && lock[i] && !lock[par2[i]]) {
        return -1;
      }
      if (!lock[i] && !lock[par1[i]]) {
        g[i].push_back(par1[i]);
      }
      if (!lock[i] && !lock[par2[i]]) {
        g[par2[i]].push_back(i);
      }
    }
    return Topo() ? (int)count(lock, lock + n, false) : -1;
  }
}

void Dfs(vector<int> *g, int *par, int u, int p) {
  par[u] = p;
  for (int v : g[u]) {
    if (v == p) continue;
    Dfs(g, par, v, u);
  }
}

void GetPar(vector<int> *g, int *par, int root) {
  Dfs(g, par, root, -1);
}

int SolveNormal(void) {
  int ans = -1;
  for (int root = 0; root < n; ++root) {
    GetPar(A, par1, root);
    GetPar(B, par2, root);
    int res = part::Solve(par1, par2);
    if (ans == -1 || (res != -1 && res < ans)) ans = res;
  }
  return ans;
}

void BuildC(int a, int b) {
  copy(A, A + n, C);
  int x = A[a][0];
  C[a].clear();
  C[x].erase(find(C[x].begin(), C[x].end(), a));
  C[a].push_back(b);
  C[b].push_back(a);
}

bool SolveSpecial(void) {
  for (int a = 0; a < n; ++a) {
    if (A[a].size() != 1) {
      continue;
    }
    for (int b = 0; b < n; ++b) {
      if (b != a) {
        BuildC(a, b);
        GetPar(C, par1, a);
        GetPar(B, par2, a);
        if (part::Solve(par1, par2) != -1) return true;
      }
    }
  }
  return false;
}

void Solve(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    A[i].clear();
    B[i].clear();
  }
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u; --v;
    A[u].push_back(v);
    A[v].push_back(u);
  }
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u; --v;
    B[u].push_back(v);
    B[v].push_back(u);
  }
  int ans = SolveNormal();
  if (ans != -1) {
    printf("%d\n", ans);
    return;
  }
  if (SolveSpecial()) {
    printf("%d\n", n);
    return;
  }
  printf("-1\n");
}

int main(void) {
  int T;
  scanf("%d", &T);
  while (T--) {
    Solve();
  }
  return 0;
}

### Prompt

Please formulate a cpp solution to the following 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

### Response

```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <queue>
#define FILL(a, n, x) memset((a), (x), sizeof ((a)[0]) * (n))
#define FILLA(a, x) memset((a), (x), sizeof (a))
#define COPY(a, n, b) memcpy((b), (a), sizeof ((a)[0]) * (n))
#define COPYA(a, b) memcpy((b), (a), sizeof (a))
using namespace std;

typedef pair<int, int> pii;
typedef long long li;
typedef unsigned long long lu;
const int inf = ~0U >> 2;
const li infl = ~0LLU >> 2;

template <class T> inline void Min(T &x, T y) { if (y < x) x = y; }
template <class T> inline void Max(T &x, T y) { if (y > x) x = y; }

// const int mod = 1e9 + 7;
// inline int Add(int x) { return x >= mod ? x - mod : x; }
// inline void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
// inline int Sub(int x) { return x < 0 ? x + mod : x; }
// inline void Sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
// inline int Mul(int x, int y) { return (int)((li)x * y % mod); }
// inline int Mul(int x, int y, int z) { return Mul(x, Mul(y, z)); }
// int Pow(int x, int y) { int z = 1;
//   for (; y; y >>= 1, x = Mul(x, x)) { if (y & 1) z = Mul(z, x); } return z; }
// inline int Inv(int x) { return Pow(x, mod - 2); }
// inline int Fix(li x) { x %= mod; if (x < 0) x += mod; return (int)x; }
// inline int Fix(int x) { x %= mod; if (x < 0) x += mod; return x; }

// ----------------------------------------

const int maxn = 50;

int n;
vector<int> A[maxn], B[maxn], C[maxn];
int par1[maxn], par2[maxn];

namespace part {
  vector<int> g[maxn];
  bool lock[maxn];
  int vis[maxn];
  bool cycle;

  void Dfs(int u) {
    if (vis[u] == 2) return;
    if (vis[u] == 1) {
      cycle = true;
      return;
    }
    vis[u] = 1;
    for (int v : g[u]) {
      Dfs(v);
      if (cycle) return;
    }
    vis[u] = 2;
  }

  bool Topo(void) {
    FILL(vis, n, 0);
    cycle = false;
    for (int i = 0; i < n; ++i) {
      Dfs(i);
      if (cycle) return false;
    }
    return true;
  }
  
  int Solve(int *par1, int *par2) {
    // should have the same root
    for (int i = 0; i < n; ++i) {
      g[i].clear();
    }
    for (int i = 0; i < n; ++i) {
      lock[i] = (par1[i] == par2[i]);
    }
    for (int i = 0; i < n; ++i) {
      if (par1[i] != -1 && lock[i] && !lock[par1[i]]) {
        return -1;
      }
      if (par2[i] != -1 && lock[i] && !lock[par2[i]]) {
        return -1;
      }
      if (!lock[i] && !lock[par1[i]]) {
        g[i].push_back(par1[i]);
      }
      if (!lock[i] && !lock[par2[i]]) {
        g[par2[i]].push_back(i);
      }
    }
    return Topo() ? (int)count(lock, lock + n, false) : -1;
  }
}

void Dfs(vector<int> *g, int *par, int u, int p) {
  par[u] = p;
  for (int v : g[u]) {
    if (v == p) continue;
    Dfs(g, par, v, u);
  }
}

void GetPar(vector<int> *g, int *par, int root) {
  Dfs(g, par, root, -1);
}

int SolveNormal(void) {
  int ans = -1;
  for (int root = 0; root < n; ++root) {
    GetPar(A, par1, root);
    GetPar(B, par2, root);
    int res = part::Solve(par1, par2);
    if (ans == -1 || (res != -1 && res < ans)) ans = res;
  }
  return ans;
}

void BuildC(int a, int b) {
  copy(A, A + n, C);
  int x = A[a][0];
  C[a].clear();
  C[x].erase(find(C[x].begin(), C[x].end(), a));
  C[a].push_back(b);
  C[b].push_back(a);
}

bool SolveSpecial(void) {
  for (int a = 0; a < n; ++a) {
    if (A[a].size() != 1) {
      continue;
    }
    for (int b = 0; b < n; ++b) {
      if (b != a) {
        BuildC(a, b);
        GetPar(C, par1, a);
        GetPar(B, par2, a);
        if (part::Solve(par1, par2) != -1) return true;
      }
    }
  }
  return false;
}

void Solve(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    A[i].clear();
    B[i].clear();
  }
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u; --v;
    A[u].push_back(v);
    A[v].push_back(u);
  }
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u; --v;
    B[u].push_back(v);
    B[v].push_back(u);
  }
  int ans = SolveNormal();
  if (ans != -1) {
    printf("%d\n", ans);
    return;
  }
  if (SolveSpecial()) {
    printf("%d\n", n);
    return;
  }
  printf("-1\n");
}

int main(void) {
  int T;
  scanf("%d", &T);
  while (T--) {
    Solve();
  }
  return 0;
}

```