LCA

정점이 $1$번부터 $N$번까지 번호가 붙은 트리가 주어진다. 트리는 $1$번 정점을 루트로 한다. 각 질의 $(u,v)$에 대해 $u$와 $v$의 가장 낮은 공통 조상을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_Q\ b_Q$

각 질의의 답을 한 줄에 하나씩 출력한다.

• $1 \leq N,Q \leq 200\ 000$.
• $1 \leq u_i,v_i \leq N$ ($1 \leq i \leq N-1$).
• 입력 간선들은 트리를 이룬다.
• $1 \leq a_j,b_j \leq N$ ($1 \leq j \leq Q$).