10099 LCA Gold III

문제

N개의 노드로 이루어진 루트가 1인 트리에서 두 노드의 최소 공통 조상(LCA)을 구하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 50,000)이 주어진다. 다음 N-1줄에 트리의 간선이 주어진다. 다음 줄에 쿼리 수 M이 주어지고, M줄에 두 노드가 주어진다.

출력

각 쿼리의 LCA를 출력한다.

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 8
8 15
11 3

2
4
2
3
3
1