가장 가까운 공통 조상 2

정점이 $N$개인 트리가 주어진다($2 \le N \le 100{,}000$). 각 정점에는 1번부터 $N$번까지 번호가 붙어 있고, 루트는 1번이다.

노드 쌍이 $M$개 주어질 때($1 \le M \le 100{,}000$), 각 쌍마다 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 두 노드의 공통 조상 가운데 루트에서 가장 먼 정점이 가장 가까운 공통 조상이다.

정점은 자기 자신의 조상으로 본다. 그래서 한 정점이 다른 정점의 조상이면 답은 그 조상 정점이다.

첫째 줄에 노드의 개수 $N$이 주어진다. 다음 $N-1$개 줄에는 트리에서 서로 연결된 두 정점의 번호가 주어진다. 한 줄에 적힌 두 정점은 부모, 자식 순서가 아닐 수도 있다.

그 다음 줄에 쌍의 개수 $M$이 주어지고, 이어지는 $M$개 줄에 가장 가까운 공통 조상을 구할 정점 쌍이 주어진다.

$M$개의 줄에 입력받은 순서대로 각 정점 쌍의 가장 가까운 공통 조상 번호를 출력한다.