树上跳转

【题目描述】

给定一棵有 $N$ 个顶点的树，其中第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。依次处理 $Q$ 个查询：

• $s$ $t$ $i$：设树上从 $s$ 到 $t$ 的最短路径为 $(v_0, v_1, \ldots, v_k)$（$v_0 = s$，$v_k = t$），输出 $v_i$。若 $i>k$，输出 -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}$

【输出】

对每个查询输出一行一个整数，即对应的答案。

【输入样例】

8 13
0 1
1 2
2 3
1 4
4 7
1 5
2 6
5 5 0
5 5 1
4 3 0
4 3 1
4 3 2
4 3 3
4 3 4
6 7 0
6 7 1
6 7 2
6 7 3
6 7 4
6 7 5

【输出样例】

5
-1
4
1
2
3
-1
6
2
1
4
7
-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$

【来源】

Library Checker（yosupo06） jump_on_tree