Lowest Common Ancestor 2

A tree with $N$ vertices is given ($2 \le N \le 100{,}000$). The vertices are numbered 1 to $N$, and vertex 1 is the root.

You are given $M$ pairs of nodes ($1 \le M \le 100{,}000$). For each pair, print the number of the lowest common ancestor of the two nodes. Among all common ancestors of the two nodes, the lowest common ancestor is the one farthest from the root.

A vertex is an ancestor of itself. So if one vertex of a pair is an ancestor of the other, the answer is that ancestor.

The first line contains the number of nodes $N$. Each of the next $N-1$ lines contains the numbers of two vertices that are connected in the tree. The two vertices on a line are not necessarily written in parent, child order.

The next line contains the number of pairs $M$, and each of the following $M$ lines contains one pair of vertices whose lowest common ancestor you must find.

Print $M$ lines. On each line print the number of the lowest common ancestor of the corresponding pair, in the order the pairs are given.