Lowest Common Ancestor

You are given a tree with $N$ vertices. The vertices are numbered from 1 to $N$, and vertex 1 is the root.

The lowest common ancestor of two vertices $u$ and $v$ is the vertex that is an ancestor of both and lies farthest from the root. A vertex counts as an ancestor of itself here.

You are given $M$ pairs of vertices. For each pair, find the number of its lowest common ancestor.

The first line contains the number of vertices $N$ ($2 \le N \le 50000$).

Each of the next $N-1$ lines contains the numbers of two vertices joined by an edge. An edge is not guaranteed to be given in parent then child order.

The next line contains the number of queries $M$ ($1 \le M \le 10000$). Each of the following $M$ lines contains one pair of vertices. The two vertices in a pair may be the same.

Print $M$ lines. On the $i$-th line print the number of the lowest common ancestor of the $i$-th pair given in the input.