최소 공통 조상

$N$개의 정점으로 이루어진 루트 있는 트리가 주어진다. 루트는 정점 $0$이고, 정점 $i$의 부모는 $p_i$이다. 다음과 같이 $Q$개의 쿼리를 처리한다:

• $u$ $v$: 정점 $u$와 $v$의 LCA을 출력한다.

제약 조건

• $2 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $0 \leq p_i < i$
• $0 \leq u < v \leq N - 1$

$N$ $Q$
$p_1$ $p_2$ ... $p_{N-1}$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{Q - 1}$ $v_{Q - 1}$

$u$ $v$: 정점 $u$와 $v$의 LCA을 출력한다.