← 返回题目列表

Codeforces · 1006/E

E. 军事问题

中文机器翻译题面 查看原题

在这个问题中,您将必须帮助 Berland 军队组织他们的指挥传递系统。

Berland军队中有$$$n$$$军官。大副是军队的统帅,没有任何上级。其他每一位军官都有一位直接上级。如果军官$$$a$$$是军官$$$b$$$的直接上级,那么我们也可以说军官$$$b$$$是军官$$$a$$$的直接下属。

如果满足以下条件之一,则官员 $$$x$$$ 被视为官员 $$$y$$$ 的下属(直接或间接):

- 官员$$$y$$$是官员$$$x$$$的直接上级;
- the direct superior of officer $$$x$$$ is a subordinate of officer $$$y$$$.

For example, on the picture below the subordinates of the officer $$$3$$$ are: $$$5, 6, 7, 8, 9$$$.

贝尔兰军队的组织结构是这样的,除了指挥官之外,每个军官都是军队指挥官的下属。

正式地,让我们将 Berland 军队表示为一棵由 $$$n$$$ 顶点组成的树,其中顶点 $$$u$$$ 对应于军官 $$$u$$$。 The parent of vertex $$$u$$$ corresponds to the direct superior of officer $$$u$$$. The root (which has index $$$1$$$) corresponds to the commander of the army.

Berland War Ministry 命令你对 $$$q$$$ 查询给出答案,第 $$$i$$$ 查询给出为 $$$(u_i, k_i)$$$,其中 $$$u_i$$$ 是某个军官,$$$k_i$$$ 是一个正整数。

To process the $$$i$$$-th query imagine how a command from $$$u_i$$$ spreads to the subordinates of $$$u_i$$$. Typical DFS (depth first search) algorithm is used here.

Suppose the current officer is $$$a$$$ and he spreads a command. Officer $$$a$$$ chooses $$$b$$$ — one of his direct subordinates (i.e. a child in the tree) who has not received this command yet. If there are many such direct subordinates, then $$$a$$$ chooses the one having minimal index. Officer $$$a$$$ gives a command to officer $$$b$$$. Afterwards, $$$b$$$ uses exactly the same algorithm to spread the command to its subtree. After $$$b$$$ finishes spreading the command, officer $$$a$$$ chooses the next direct subordinate again (using the same strategy).当军官$$$a$$$无法选择尚未收到此命令的直属下属时,军官$$$a$$$完成命令的传播。

Let's look at the following example:

If officer $$$1$$$ spreads a command, officers receive it in the following order: $$$[1, 2, 3, 5 ,6, 8, 7, 9, 4]$$$.

If officer $$$3$$$ spreads a command, officers receive it in the following order: $$$[3, 5, 6, 8, 7, 9]$$$.

If officer $$$7$$$ spreads a command, officers receive it in the following order: $$$[7, 9]$$$.

If officer $$$9$$$ spreads a command, officers receive it in the following order: $$$[9]$$$.

要回答第 $$$i$$$ 查询 $$$(u_i, k_i)$$$,请构造一个序列,该序列描述如果第 $$$u_i$$$ 军官传播命令,军官将收到命令的顺序。 Return the $$$k_i$$$-th element of the constructed list or -1 if there are fewer than $$$k_i$$$ elements in it.

You should process queries independently. A query doesn't affect the following queries.

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$) — Berland 军队的军官人数和查询次数。

输入的第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$),其中 $$$p_i$$$ 是索引为 $$$i$$$ 的军官的直接上级索引。 The commander has index $$$1$$$ and doesn't have any superiors.

The next $$$q$$$ lines describe the queries.第 $$$i$$$ 查询作为一对 ($$$u_i, k_i$$$) ($$$1 \le u_i, k_i \le n$$$) 给出,其中 $$$u_i$$$ 是开始传播命令的军官的索引,$$$k_i$$$ 是命令传播序列中所需军官的索引。

输出

打印 $$$q$$$ 数字,其中第 $$$i$$$ 数字是列表中位置 $$$k_i$$$ 的军官,该列表描述了如果命令开始从军官 $$$u_i$$$ 传播,军官将收到命令的顺序。 Print "-1" if the number of officers which receive the command is less than $$$k_i$$$.

You should process queries independently. They do not affect each other.

示例

输入 #1

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

输出 #1

3
6
8
-1
9
4