{"problem":{"name":"E. Military Problem","description":{"content":"In this problem you will have to help Berland army with organizing their command delivery system. There are $n$ officers in Berland army. The first officer is the commander of the army, and he does n","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1006E"},"statements":[{"statement_type":"Markdown","content":"In this problem you will have to help Berland army with organizing their command delivery system.\n\nThere are $n$ officers in Berland army. The first officer is the commander of the army, and he does not have any superiors. Every other officer has exactly one direct superior. If officer $a$ is the direct superior of officer $b$, then we also can say that officer $b$ is a direct subordinate of officer $a$.\n\nOfficer $x$ is considered to be a subordinate (direct or indirect) of officer $y$ if one of the following conditions holds:\n\n*   officer $y$ is the direct superior of officer $x$;\n*   the direct superior of officer $x$ is a subordinate of officer $y$.\n\nFor example, on the picture below the subordinates of the officer $3$ are: $5, 6, 7, 8, 9$.\n\nThe structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army.\n\nFormally, let's represent Berland army as a tree consisting of $n$ vertices, in which vertex $u$ corresponds to officer $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.\n\nBerland War Ministry has ordered you to give answers on $q$ queries, the $i$\\-th query is given as $(u_i, k_i)$, where $u_i$ is some officer, and $k_i$ is a positive integer.\n\nTo 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.\n\nSuppose 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). When officer $a$ cannot choose any direct subordinate who still hasn't received this command, officer $a$ finishes spreading the command.\n\nLet's look at the following example:\n\n<center>![image](https://espresso.codeforces.com/a26785a0921dbecc44400765603c6f8cf526d8f4.png)</center>If officer $1$ spreads a command, officers receive it in the following order: $[1, 2, 3, 5 ,6, 8, 7, 9, 4]$.\n\nIf officer $3$ spreads a command, officers receive it in the following order: $[3, 5, 6, 8, 7, 9]$.\n\nIf officer $7$ spreads a command, officers receive it in the following order: $[7, 9]$.\n\nIf officer $9$ spreads a command, officers receive it in the following order: $[9]$.\n\nTo answer the $i$\\-th query $(u_i, k_i)$, construct a sequence which describes the order in which officers will receive the command if the $u_i$\\-th officer spreads it. Return the $k_i$\\-th element of the constructed list or _\\-1_ if there are fewer than $k_i$ elements in it.\n\nYou should process queries independently. A query doesn't affect the following queries.\n\n## Input\n\nThe first line of the input contains two integers $n$ and $q$ ($2 \\le n \\le 2 \\cdot 10^5, 1 \\le q \\le 2 \\cdot 10^5$) — the number of officers in Berland army and the number of queries.\n\nThe second line of the input contains $n - 1$ integers $p_2, p_3, \\dots, p_n$ ($1 \\le p_i &lt; i$), where $p_i$ is the index of the direct superior of the officer having the index $i$. The commander has index $1$ and doesn't have any superiors.\n\nThe next $q$ lines describe the queries. The $i$\\-th query is given as a pair ($u_i, k_i$) ($1 \\le u_i, k_i \\le n$), where $u_i$ is the index of the officer which starts spreading a command, and $k_i$ is the index of the required officer in the command spreading sequence.\n\n## Output\n\nPrint $q$ numbers, where the $i$\\-th number is the officer at the position $k_i$ in the list which describes the order in which officers will receive the command if it starts spreading from officer $u_i$. Print \"_\\-1_\" if the number of officers which receive the command is less than $k_i$.\n\nYou should process queries independently. They do not affect each other.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在本题中，你需要帮助贝兰军队组织他们的命令传递系统。\n\n贝兰军队中有 $n$ 名军官。第一名军官是军队的指挥官，他没有上级。其他每名军官都恰好有一个直接上级。如果军官 $a$ 是军官 $b$ 的直接上级，则我们也称军官 $b$ 是军官 $a$ 的直接下属。\n\n军官 $x$ 被认为是军官 $y$ 的下属（直接或间接），当且仅当满足以下条件之一：\n\n例如，在下图中，军官 $3$ 的下属为：$5, 6, 7, 8, 9$。\n\n贝兰军队的结构保证了除指挥官外，每名军官都是指挥官的下属。\n\n形式化地，我们将贝兰军队表示为一棵包含 $n$ 个顶点的树，其中顶点 $u$ 对应军官 $u$。顶点 $u$ 的父节点对应军官 $u$ 的直接上级。根节点（索引为 $1$）对应军队的指挥官。\n\n贝兰战争部要求你回答 $q$ 个查询，第 $i$ 个查询为 $(u_i, k_i)$，其中 $u_i$ 是某位军官，$k_i$ 是一个正整数。\n\n处理第 $i$ 个查询时，想象命令从 $u_i$ 开始向其下属传播的过程。此处使用典型的 DFS（深度优先搜索）算法。\n\n假设当前军官为 $a$，他正在传播命令。军官 $a$ 选择一个尚未收到该命令的直接下属 $b$（即树中的子节点）。若有多个这样的直接下属，则选择索引最小的那个。军官 $a$ 将命令传达给军官 $b$。随后，$b$ 使用完全相同的算法将其子树中的命令传播出去。当 $b$ 完成传播后，军官 $a$ 再次选择下一个尚未收到命令的直接下属（使用相同策略）。当军官 $a$ 无法再选择任何尚未收到命令的直接下属时，他停止传播命令。\n\n我们来看一个例子：\n\n如果军官 $1$ 传播命令，军官接收命令的顺序为：$[ 1, 2, 3, 5, 6, 8, 7, 9, 4 ]$。\n\n如果军官 $3$ 传播命令，军官接收命令的顺序为：$[ 3, 5, 6, 8, 7, 9 ]$。\n\n如果军官 $7$ 传播命令，军官接收命令的顺序为：$[ 7, 9 ]$。\n\n如果军官 $9$ 传播命令，军官接收命令的顺序为：$[ 9 ]$。\n\n对于第 $i$ 个查询 $(u_i, k_i)$，构造一个序列，描述当第 $u_i$ 名军官开始传播命令时，军官接收命令的顺序。返回该序列中第 $k_i$ 个元素，若序列长度小于 $k_i$，则返回 _-1_。\n\n你应当独立处理每个查询。一个查询不会影响后续查询。\n\n输入的第一行包含两个整数 $n$ 和 $q$ ($2 \\leq n \\leq 2 \\cdot 10^5, 1 \\leq q \\leq 2 \\cdot 10^5$) —— 贝兰军队的军官数量和查询数量。\n\n第二行包含 $n - 1$ 个整数 $p_2, p_3, \\dots, p_n$ ($1 \\leq p_i < i$)，其中 $p_i$ 是索引为 $i$ 的军官的直接上级的索引。指挥官的索引为 $1$，没有上级。\n\n接下来的 $q$ 行描述查询。第 $i$ 个查询由一对 $(u_i, k_i)$ 给出 ($1 \\leq u_i, k_i \\leq n$)，其中 $u_i$ 是开始传播命令的军官索引，$k_i$ 是所需命令传播序列中的位置索引。\n\n输出 $q$ 个数字，其中第 $i$ 个数字是当命令从军官 $u_i$ 开始传播时，序列中第 $k_i$ 个位置的军官编号。如果接收命令的军官数量少于 $k_i$，则输出 \"_-1_\"。\n\n你应当独立处理每个查询。它们互不影响。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $q$ ($2 \\leq n \\leq 2 \\cdot 10^5, 1 \\leq q \\leq 2 \\cdot 10^5$) —— 贝兰军队的军官数量和查询数量。第二行包含 $n - 1$ 个整数 $p_2, p_3, \\dots, p_n$ ($1 \\leq p_i < i$)，其中 $p_i$ 是索引为 $i$ 的军官的直接上级的索引。指挥官的索引为 $1$，没有上级。接下来的 $q$ 行描述查询。第 $i$ 个查询由一对 $(u_i, k_i)$ 给出 ($1 \\leq u_i, k_i \\leq n$)，其中 $u_i$ 是开始传播命令的军官索引，$k_i$ 是所需命令传播序列中的位置索引。\n\n## Output\n\n输出 $q$ 个数字，其中第 $i$ 个数字是当命令从军官 $u_i$ 开始传播时，序列中第 $k_i$ 个位置的军官编号。如果接收命令的军官数量少于 $k_i$，则输出 \"_-1_\"。你应当独立处理每个查询。它们互不影响。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $, and vertex $ 1 $ is the root (commander).  \nFor each officer $ i \\in \\{2, \\dots, n\\} $, let $ p_i \\in \\{1, \\dots, i-1\\} $ denote the unique parent (direct superior) of $ i $.  \nFor each officer $ u \\in V $, let $ \\text{children}(u) \\subseteq V $ denote the set of direct subordinates (children) of $ u $, sorted in increasing order of their indices.  \n\nLet $ \\text{DFS}(u) $ denote the sequence of officers visited in the DFS traversal starting at $ u $, where at each node, children are visited in increasing index order. This sequence includes $ u $ and all its descendants, in the order they are discovered.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq q \\leq 2 \\cdot 10^5 $  \n3. For each $ i \\in \\{2, \\dots, n\\} $: $ 1 \\leq p_i < i $  \n4. For each query $ (u_i, k_i) $: $ 1 \\leq u_i \\leq n $, $ 1 \\leq k_i \\leq n $\n\n**Objective**  \nFor each query $ (u_i, k_i) $, compute the $ k_i $-th element of $ \\text{DFS}(u_i) $. If $ |\\text{DFS}(u_i)| < k_i $, return $ -1 $.  \n\nLet $ S(u) = \\text{DFS}(u) $, and define:  \n$$\n\\text{answer}(u_i, k_i) =\n\\begin{cases}\nS(u_i)[k_i] & \\text{if } k_i \\leq |S(u_i)| \\\\\n-1 & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1006E","tags":["dfs and similar","graphs","trees"],"sample_group":[["9 6\n1 1 1 3 5 3 5 7\n3 1\n1 5\n3 4\n7 3\n1 8\n1 9","3\n6\n8\n-1\n9\n4"]],"created_at":"2026-03-03 11:00:39"}}