Tree LCA 2

Problem Description

You are given a tree of $n$ nodes rooted at node $1$; the nodes are numbered $1$ to $n$. There are $m$ queries; for each query $(u, v)$, output the lowest common ancestor of node $u$ and node $v$.

Input Format

The first line contains one integer $n$, the number of nodes.

The next $n - 1$ lines each contain two integers $x, y$, meaning there is an edge between node $x$ and node $y$.

The input is guaranteed to form a tree.

The next line contains one integer $m$, the number of queries.

The next $m$ lines each contain two integers $u, v$, representing one query.

Output Format

Output $m$ lines in total; for each query output one line containing one integer: the index of the lowest common ancestor of the two given nodes.

Sample Input

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

Sample Output

1
1

Constraints

For all data, it is guaranteed that $1 \le n, m \le 100000,\ 1 \le u, v \le n$.