Problem: Sigma and Sugim are playing a game.

The game is played on a graph with N vertices numbered 1 through N. The graph has N-1 red edges and N-1 blue edges, and the N-1 edges in each color forms a tree. The red edges are represented by pairs of integers (a_i, b_i), and the blue edges are represented by pairs of integers (c_i, d_i).

Each player has his own piece. Initially, Sigma's piece is at vertex X, and Sugim's piece is at vertex Y.

The game is played in turns, where turns are numbered starting from turn 1. Sigma takes turns 1, 3, 5, ..., and Sugim takes turns 2, 4, 6, ....

In each turn, the current player either moves his piece, or does nothing. Here, Sigma can only move his piece to a vertex that is directly connected to the current vertex by a red edge. Similarly, Sugim can only move his piece to a vertex that is directly connected to the current vertex by a blue edge.

When the two pieces come to the same vertex, the game ends immediately. If the game ends just after the operation in turn i, let i be the total number of turns in the game.

Sigma's objective is to make the total number of turns as large as possible, while Sugim's objective is to make it as small as possible.

Determine whether the game will end in a finite number of turns, assuming both players plays optimally to achieve their respective objectives. If the answer is positive, find the number of turns in the game.

Constraints

* 2 ≦ N ≦ 200,000
* 1 ≦ X, Y ≦ N
* X \neq Y
* 1 ≦ a_i, b_i, c_i, d_i ≦ N
* The N-1 edges in each color (red and blue) forms a tree.

Input

The input is given from Standard Input in the following format:


N X Y
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
c_1 d_1
c_2 d_2
:
c_{N-1} d_{N-1}


Output

If the game will end in a finite number of turns, print the number of turns. Otherwise, print `-1`.

Examples

Input

4 1 2
1 2
1 3
1 4
2 1
2 3
1 4


Output

4


Input

3 3 1
1 2
2 3
1 2
2 3


Output

4


Input

4 1 2
1 2
3 4
2 4
1 2
3 4
1 3


Output

2


Input

4 2 1
1 2
3 4
2 4
1 2
3 4
1 3


Output

-1


Input

5 1 2
1 2
1 3
1 4
4 5
2 1
1 3
1 5
5 4


Output

6

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 * 
 * @author daltao
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "daltao", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            PrintWriter out = new PrintWriter(outputStream);
            TaskE solver = new TaskE();
            solver.solve(1, in, out);
            out.close();
        }
    }
    static class TaskE {
        int inf = (int) 1e8;

        public void solve(int testNumber, FastInput in, PrintWriter out) {
            int n = in.readInt();

            Node[] nodes = new Node[n + 1];
            for (int i = 1; i <= n; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
            }

            Node x = nodes[in.readInt()];
            Node y = nodes[in.readInt()];

            List<Query> querys = new ArrayList<>(n);
            for (int i = 1; i < n; i++) {
                Node a = nodes[in.readInt()];
                Node b = nodes[in.readInt()];
                a.red.add(b);
                b.red.add(a);
                Query q = new Query();
                q.a = a;
                q.b = b;
                querys.add(q);
                a.lcaQueries.add(q);
                b.lcaQueries.add(q);
            }

            for (int i = 1; i < n; i++) {
                Node a = nodes[in.readInt()];
                Node b = nodes[in.readInt()];
                a.blue.add(b);
                b.blue.add(a);
            }

            dfsForDepth(y, null, 0);
            dfsForLca(y, null);

            for (Query q : querys) {
                if (q.a.depth + q.b.depth - 2 * q.lca.depth >= 3) {
                    q.a.escape = q.b.escape = true;
                }
            }

            int escape = escape(x, null, 0);
            if (escape == inf) {
                out.println(-1);
            } else {
                out.println(escape * 2);
            }
        }

        public void dfsForLca(Node root, Node fa) {
            root.blue.remove(fa);
            root.lca = root;
            root.visited = true;
            for (Node node : root.blue) {
                if (node == fa) {
                    continue;
                }
                dfsForLca(node, root);
                Node.merge(node, root);
                root.find().lca = root;
            }

            for (Query q : root.lcaQueries) {
                Node other = q.a == root ? q.b : q.a;
                if (!other.visited) {
                    continue;
                }
                q.lca = other.find().lca;
            }
        }

        public int escape(Node root, Node fa, int depth) {
            root.red.remove(fa);
            if (root.depth <= depth) {
                return root.depth;
            }
            if (root.escape) {
                return inf;
            }
            int max = root.depth;
            for (Node node : root.red) {
                max = Math.max(max, escape(node, root, depth + 1));
            }
            return max;
        }

        public void dfsForDepth(Node root, Node fa, int depth) {
            root.blue.remove(fa);
            root.depth = depth;
            for (Node node : root.blue) {
                dfsForDepth(node, root, depth + 1);
            }
        }

    }
    static class Query {
        Node a;
        Node b;
        Node lca;

    }
    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
    static class Node {
        List<Node> red = new ArrayList<>();
        List<Node> blue = new ArrayList<>();
        List<Query> lcaQueries = new ArrayList<>();
        boolean escape;
        int depth;
        int id;
        boolean visited = false;
        Node p = this;
        int rank;
        Node lca;

        Node find() {
            return p == p.p ? p : (p = p.find());
        }

        static void merge(Node a, Node b) {
            a = a.find();
            b = b.find();
            if (a == b) {
                return;
            }
            if (a.rank == b.rank) {
                a.rank++;
            }
            if (a.rank > b.rank) {
                b.p = a;
            } else {
                a.p = b;
            }
        }

    }
}