LCA와 쿼리

N개의 정점으로 이루어진 트리 T가 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

• r u v: T의 루트를 r로 잡았을 때, u와 v의 최소 공통 조상(LCA)을 출력한다.

정점에는 1번부터 N번까지 번호가 붙어 있다. 루트를 r로 잡으면 조상 관계가 r을 기준으로 다시 정해지므로, u와 v가 같아도 r이 달라지면 답이 달라진다. 루트가 r일 때 u와 v의 LCA는 r에서 u로 가는 경로와 r에서 v로 가는 경로에 모두 놓인 정점 중 r에서 가장 먼 정점이다.

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v(1 ≤ u, v ≤ N)가 주어진다. u와 v는 그 간선이 잇는 두 정점이다.

다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 이어지는 M개의 줄에는 쿼리를 나타내는 세 정수 r, u, v(1 ≤ r, u, v ≤ N)가 주어진다.

각 쿼리마다 한 줄에 하나씩 LCA인 정점의 번호를 출력한다.