Lowest Common Ancestor

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Given a rooted tree with \(n\) vertices, numbered from \(1\) to \(n\). The root of the tree is vertex \(1\).

You need to answer \(q\) queries — for a pair of vertices \(x\), \(y\), find their lowest common ancestor.

Input

The first line contains an integer \(n\) — the number of vertices in the tree.

The next \(n - 1\) lines each contain two integers \(u\), \(v\) — the numbers of vertices connected by an edge.

Next is given an integer \(q\) — the number of queries.

The next \(q\) lines each contain two integers \(x\), \(y\) — the numbers of vertices in the query.

Output

In \(q\) lines, print one integer for each query — the number of the lowest common ancestor of vertices \(x\) and \(y\).

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le q \le 2 \cdot 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 7 1 2 1 3 2 4 2 5 3 6 7 4 7 7 6 7 7 5 7 2 3 7 3 4 5	4 1 7 2 1 1 2

Notes

• The lowest common ancestor of vertices \(4\) and \(7\) is vertex \(4\).

• The lowest common ancestor of vertices \(7\) and \(6\) is vertex \(1\).

• The lowest common ancestor of vertices \(7\) and \(7\) is vertex \(7\).

• The lowest common ancestor of vertices \(5\) and \(7\) is vertex \(2\).

• The lowest common ancestor of vertices \(2\) and \(3\) is vertex \(1\).

• The lowest common ancestor of vertices \(7\) and \(3\) is vertex \(1\).

• The lowest common ancestor of vertices \(4\) and \(5\) is vertex \(2\).