#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

vector<vector<bool>> a;
vector<vector<bool>> b;
vector<int> d;
vector<int> xxx;
vector<int> parent;
vector<bool> used;
vector<bool> good;

void add_edge(int x, int y) {
//    cout << "add " << x << " " << y << "\n";
    assert(!a[x][y]);
    a[x][y] = a[y][x] = 1;
    xxx[x] ^= y;
    xxx[y] ^= x;
    d[x]++;
    d[y]++;
}

vector<pair<int, int>> queue;
vector<bool> in_queue;

void update_d(int x) {
//    cout << "ud " << x << "\n";
    if (d[x] == 1 && !used[x] && !good[x] && !in_queue[x]) {
        for (int y = 0; y < d.size(); y++) {
            if (b[x][y] && good[y]) {
                in_queue[x] = true;
                queue.push_back({x, y});
                break;
            }
        }
    }
}

void update_g(int y) {
//    cout << "ug " << y << "\n";
    for (int x = 0; x < d.size(); x++) {
        if (b[x][y]) {
            if (d[x] == 1 && !used[x] && !good[x] && !in_queue[x]) {
                in_queue[x] = true;
                queue.push_back({x, y});
            }
        }
    }
}

void remove_edge(int x, int y) {
//    cout << "rem " << x << " " << y << "\n";
    assert(a[x][y]);
    a[x][y] = a[y][x] = 0;
    xxx[x] ^= y;
    xxx[y] ^= x;
    d[x]--;
    d[y]--;
    update_d(x);
    update_d(y);
}


void dfs(int x, int p) {
    parent[x] = p;
    if (p == -1) {
        good[x] = true;
    } else {
        good[x] = good[p] && b[x][p];
    }
    for (int y = 0; y < d.size(); y++) {
        if (a[x][y] && y != p) {
            dfs(y, x);
        }
    }
}

void solve_test() {
    int n;
    cin >> n;
    a.assign(n, vector<bool>(n));
    b.assign(n, vector<bool>(n));
    d.assign(n, 0);
    xxx.assign(n, 0);
    for (int i = 0; i < 2 * (n - 1); i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (i < n - 1) {
            add_edge(x, y);
//            a[x][y] = a[y][x] = 1;
        } else {
            b[x][y] = b[y][x] = 1;
        }
    }
    if (a == b) {
        cout << 0 << "\n";
        return;
    }
    auto a_save = a;
    auto d_save = d;
    auto xxx_save = xxx;

    int res = 1000;
    for (int x = 0; x < n; x++) {
        a = a_save;
        d = d_save;
        xxx = xxx_save;
        if (d[x] != 1) continue;
        for (int y = 0; y < n; y++) {
            if (y == x) continue;

//            cout << x << " " << y << std::endl;

            a = a_save;
            d = d_save;
            xxx = xxx_save;
            parent.assign(n, -1);
            used.assign(n, 0);
            good.assign(n, 0);
            queue.resize(0);
            in_queue.assign(n, 0);

            remove_edge(x, xxx[x]);
            add_edge(x, y);

            int s = 1;

            used[x] = true;

            dfs(x, -1);

            for (int i = 0; i < n; i++) {
                if (good[i]) update_g(i);
            }

            for (int i = 0; i < queue.size(); i++) {
                int xx = queue[i].first;
                int yy = queue[i].second;
                remove_edge(xx, xxx[xx]);
                add_edge(xx, yy);
                s++;
                good[xx] = true;
                update_g(xx);
            }

            if (a == b) {
                res = std::min(res, s);
            }
        }
    }
    if (res == 1000) {
        cout << -1 << "\n";
    } else {
        cout << res << "\n";
    }
}

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

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        solve_test();
    }

    return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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 <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

vector<vector<bool>> a;
vector<vector<bool>> b;
vector<int> d;
vector<int> xxx;
vector<int> parent;
vector<bool> used;
vector<bool> good;

void add_edge(int x, int y) {
//    cout << "add " << x << " " << y << "\n";
    assert(!a[x][y]);
    a[x][y] = a[y][x] = 1;
    xxx[x] ^= y;
    xxx[y] ^= x;
    d[x]++;
    d[y]++;
}

vector<pair<int, int>> queue;
vector<bool> in_queue;

void update_d(int x) {
//    cout << "ud " << x << "\n";
    if (d[x] == 1 && !used[x] && !good[x] && !in_queue[x]) {
        for (int y = 0; y < d.size(); y++) {
            if (b[x][y] && good[y]) {
                in_queue[x] = true;
                queue.push_back({x, y});
                break;
            }
        }
    }
}

void update_g(int y) {
//    cout << "ug " << y << "\n";
    for (int x = 0; x < d.size(); x++) {
        if (b[x][y]) {
            if (d[x] == 1 && !used[x] && !good[x] && !in_queue[x]) {
                in_queue[x] = true;
                queue.push_back({x, y});
            }
        }
    }
}

void remove_edge(int x, int y) {
//    cout << "rem " << x << " " << y << "\n";
    assert(a[x][y]);
    a[x][y] = a[y][x] = 0;
    xxx[x] ^= y;
    xxx[y] ^= x;
    d[x]--;
    d[y]--;
    update_d(x);
    update_d(y);
}


void dfs(int x, int p) {
    parent[x] = p;
    if (p == -1) {
        good[x] = true;
    } else {
        good[x] = good[p] && b[x][p];
    }
    for (int y = 0; y < d.size(); y++) {
        if (a[x][y] && y != p) {
            dfs(y, x);
        }
    }
}

void solve_test() {
    int n;
    cin >> n;
    a.assign(n, vector<bool>(n));
    b.assign(n, vector<bool>(n));
    d.assign(n, 0);
    xxx.assign(n, 0);
    for (int i = 0; i < 2 * (n - 1); i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (i < n - 1) {
            add_edge(x, y);
//            a[x][y] = a[y][x] = 1;
        } else {
            b[x][y] = b[y][x] = 1;
        }
    }
    if (a == b) {
        cout << 0 << "\n";
        return;
    }
    auto a_save = a;
    auto d_save = d;
    auto xxx_save = xxx;

    int res = 1000;
    for (int x = 0; x < n; x++) {
        a = a_save;
        d = d_save;
        xxx = xxx_save;
        if (d[x] != 1) continue;
        for (int y = 0; y < n; y++) {
            if (y == x) continue;

//            cout << x << " " << y << std::endl;

            a = a_save;
            d = d_save;
            xxx = xxx_save;
            parent.assign(n, -1);
            used.assign(n, 0);
            good.assign(n, 0);
            queue.resize(0);
            in_queue.assign(n, 0);

            remove_edge(x, xxx[x]);
            add_edge(x, y);

            int s = 1;

            used[x] = true;

            dfs(x, -1);

            for (int i = 0; i < n; i++) {
                if (good[i]) update_g(i);
            }

            for (int i = 0; i < queue.size(); i++) {
                int xx = queue[i].first;
                int yy = queue[i].second;
                remove_edge(xx, xxx[xx]);
                add_edge(xx, yy);
                s++;
                good[xx] = true;
                update_g(xx);
            }

            if (a == b) {
                res = std::min(res, s);
            }
        }
    }
    if (res == 1000) {
        cout << -1 << "\n";
    } else {
        cout << res << "\n";
    }
}

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

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        solve_test();
    }

    return 0;
}
```