트리 위의 점프

정점이 $N$개인 트리가 주어지며, $i$번째 간선은 정점 $a_i$와 $b_i$을 연결한다. 다음과 같이 $Q$개의 쿼리를 처리한다:

• $s$ $t$ $i$: 트리에서 $s$부터 $t$까지의 최단 경로가 $(v_0, v_1, \ldots, v_k)$일 때, $v_i$을 출력한다($v_0 = s$, $v_k = t$). $i>k$이면, -1을 출력한다.

제약 조건

• $2 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $0 \leq a_i, b_i \leq N-1$
• $a_i \neq b_i$
• $0 \leq s, t \leq N - 1$
• $0 \leq i \leq N - 1$

$N$ $Q$
$a_0$ $b_0$
$\vdots$
$a_{N-2}$ $b_{N-2}$
$s_0$ $t_0$ $i_0$
$\vdots$
$s_{Q-1}$ $t_{Q-1}$ $i_{Q-1}$

$s$ $t$ $i$: 트리에서 $s$부터 $t$까지의 최단 경로가 $(v_0, v_1, \ldots, v_k)$일 때, $v_i$을 출력한다($v_0 = s$, $v_k = t$). $i>k$이면, -1을 출력한다.