4417: 树的深搜

给定一棵 n 个节点的树。

节点的编号为 1∼n，其中 1 号节点为根节点，每个节点的编号都大于其父节点的编号。

现在，你需要回答 q 个询问。

每个询问给定两个整数 u_i, k_i。

我们希望你用 DFS（深度优先搜索）算法来遍历根节点为 u_i 的子树。

我们规定，当遍历（或回溯）到某一节点时，下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。

例如，上图实例中：

• 如果遍历根节点为 1 号节点的子树，则子树内各节点的遍历顺序为 [1,2,3,5,6,8,7,9,4]。
• 如果遍历根节点为 3 号节点的子树，则子树内各节点的遍历顺序为 [3,5,6,8,7,9]。
• 如果遍历根节点为 7 号节点的子树，则子树内各节点的遍历顺序为 [7,9]。
• 如果遍历根节点为 9 号节点的子树，则子树内各节点的遍历顺序为 [9]。

每个询问就是让你计算采用规定的 DFS 算法来遍历根节点为 u_i 的子树时，第 k_i 个被遍历到的节点的编号。

第一行包含两个整数 n, q。

第二行包含 n−1 个整数 p₂, p₃, …, p_n，其中 p_i 表示第 i 号节点的父节点的编号。

接下来 q 行，每行包含两个整数 u_i, k_i，表示一组询问。

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

3
6
8
-1
9
4