최소 공통 조상 (대용량)

N개의 정점으로 이루어진 트리에서 Q개의 LCA(최소 공통 조상) 쿼리를 처리하여라. 희소 테이블(Sparse Table) LCA를 사용해야 한다.

입력

첫째 줄에 N, 이후 N-1개의 줄에 간선 정보 u, v, 그 다음 줄에 Q, 이후 Q개의 줄에 u, v가 주어진다.

• 1 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 루트는 1번 정점이다.

출력

각 LCA 쿼리의 결과를 한 줄씩 출력한다.

예제 입력 1

7
1 2
1 3
1 4
2 5
2 6
4 7
3
5 6
5 7
2 7

예제 출력 1

2
1
1