가장 가까운 공통 조상

정점이 $N$개인 트리가 주어진다. 각 정점에는 1번부터 $N$번까지 번호가 붙어 있고, 루트는 1번이다.

두 정점 $u$와 $v$의 가장 가까운 공통 조상은 $u$의 조상이면서 동시에 $v$의 조상인 정점 가운데 루트에서 가장 멀리 떨어진 정점이다. 여기서는 정점 자신도 자기 자신의 조상으로 본다.

정점 쌍 $M$개가 주어진다. 각 쌍마다 가장 가까운 공통 조상이 몇 번인지 구한다.

첫째 줄에 정점의 개수 $N$이 주어진다 ($2 \le N \le 50000$).

다음 $N-1$개 줄에는 트리에서 간선으로 이어진 두 정점의 번호가 주어진다. 간선은 부모, 자식 순서로 주어진다는 보장이 없다.

그 다음 줄에 질의의 개수 $M$이 주어진다 ($1 \le M \le 10000$). 이어지는 $M$개 줄에는 정점 쌍이 한 줄에 하나씩 주어진다. 한 쌍의 두 정점은 같을 수도 있다.

$M$개의 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째로 주어진 쌍의 가장 가까운 공통 조상 번호를 출력한다.