p03259 AtCoder Grand Contest 027 - Grafting_33256
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
import java.io.*;
import java.util.*;

public class Main {
    FastScanner in;
    PrintWriter out;

    void fillParent(int v, int par, boolean[][] g, int[] p) {
        p[v] = par;
        for (int to = 0; to < g.length; to++) {
            if (to != par && g[v][to]) {
                fillParent(to, v, g, p);
            }
        }
    }

    void solve() {
        int tc = in.nextInt();
        for (int t = 0; t < tc; t++) {
            int n = in.nextInt();
            boolean[][] g = new boolean[n][n];
            boolean[][] gTmp = new boolean[n][n];
            for (int i = 0; i + 1 < n; i++) {
                int fr = in.nextInt() - 1;
                int to = in.nextInt() - 1;
                gTmp[fr][to] = gTmp[to][fr] = true;
            }
            boolean[][] gNeed = new boolean[n][n];
            for (int i = 0; i + 1 < n; i++) {
                int fr = in.nextInt() - 1;
                int to = in.nextInt() - 1;
                gNeed[fr][to] = gNeed[to][fr] = true;
            }
            int ans = Integer.MAX_VALUE;
            int[] parent = new int[n];
            boolean[] ok = new boolean[n];
            int[] gSz = new int[n];
            for (int root = 0; root < n; root++) {
                for (int i = 0; i < n; i++) {
                    gSz[i] = 0;
                    for (int j = 0; j < n; j++) {
                        g[i][j] = gTmp[i][j];
                        if (g[i][j]) {
                            gSz[i]++;
                        }
                    }
                }
                fillParent(root, root, gNeed, parent);
                Arrays.fill(ok, false);
                ok[root] = true;
                int cost = 0;
                while (true) {
                    boolean ch = false;
                    for (int i = 0; i < n; i++) {
                        if (!ok[i] && ok[parent[i]] && g[i][parent[i]]) {
                            ok[i] = true;
                            ch = true;
                        }
                    }
                    if (ch) {
                        continue;
                    }
                    for (int i = 0; i < n; i++) {
                        if (!ok[i] && gSz[i] == 1 && ok[parent[i]]) {
                            int curEdge = -1;
                            for (int j = 0; j < n; j++) {
                                if (g[i][j]) {
                                    curEdge = j;
                                }
                            }
                            g[i][curEdge] = g[curEdge][i] = false;
                            g[i][parent[i]] = g[parent[i]][i] = true;
                            cost++;
                            ok[i] = true;
                            gSz[parent[i]]++;
                            gSz[curEdge]--;
                            ch = true;
                            break;
                        }
                    }
                    if (!ch) {
                        break;
                    }
                }
                boolean totalOk = true;
                for (boolean z : ok) {
                    totalOk &= z;
                }
                if (totalOk) {
                    ans = Math.min(ans, cost);
                }
            }




            for (int root = 0; root < n; root++) {
                for (int connectTo = 0; connectTo < n; connectTo++) {
                    if (root == connectTo || gTmp[root][connectTo]) {
                        continue;
                    }
                    for (int i = 0; i < n; i++) {
                        gSz[i] = 0;
                        for (int j = 0; j < n; j++) {
                            g[i][j] = gTmp[i][j];
                            if (g[i][j]) {
                                gSz[i]++;
                            }
                        }
                    }
                    fillParent(root, root, gNeed, parent);
                    Arrays.fill(ok, false);
                    ok[root] = true;
                    int cost = 1;
                    if (gSz[root] != 1) {
                        continue;
                    }
                    int edgeTo =0 ;
                    while (!g[root][edgeTo]) {
                        edgeTo++;
                    }
                    g[root][edgeTo] = g[edgeTo][root] = false;
                    g[root][connectTo] = g[connectTo][root] = true;
                    gSz[edgeTo]--;
                    gSz[connectTo]++;


                    while (true) {
                        boolean ch = false;
                        for (int i = 0; i < n; i++) {
                            if (!ok[i] && ok[parent[i]] && g[i][parent[i]]) {
                                ok[i] = true;
                                ch = true;
                            }
                        }
                        if (ch) {
                            continue;
                        }
                        for (int i = 0; i < n; i++) {
                            if (!ok[i] && gSz[i] == 1 && ok[parent[i]]) {
                                int curEdge = -1;
                                for (int j = 0; j < n; j++) {
                                    if (g[i][j]) {
                                        curEdge = j;
                                    }
                                }
                                g[i][curEdge] = g[curEdge][i] = false;
                                g[i][parent[i]] = g[parent[i]][i] = true;
                                cost++;
                                ok[i] = true;
                                gSz[parent[i]]++;
                                gSz[curEdge]--;
                                ch = true;
                                break;
                            }
                        }
                        if (!ch) {
                            break;
                        }
                    }
                    boolean totalOk = true;
                    for (boolean z : ok) {
                        totalOk &= z;
                    }
                    if (totalOk) {
                        ans = Math.min(ans, cost);
                    }
                }
            }




            out.println(ans == Integer.MAX_VALUE ? -1 : ans);
        }
    }


    void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}