{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e在这个问题中,你需要帮助 Berland 军队组织他们的指挥传递系统。\u003c/p\u003e\u003cp\u003eBerland 军队中有 $$$n$$$ 名军官。第一名军官是军队的指挥官,他没有任何上级。每个其他军官都恰好有一个直接上级。如果军官 $$$a$$$ 是军官 $$$b$$$ 的直接上级,那么我们也可以说军官 $$$b$$$ 是军官 $$$a$$$ 的直接下属。\u003c/p\u003e\u003cp\u003e如果军官 $$$x$$$ 满足以下条件之一,就被认为是军官 $$$y$$$ 的下属(直接或间接):\u003c/p\u003e\u003cul\u003e \u003cli\u003e 军官 $$$y$$$ 是军官 $$$x$$$ 的直接上级; \u003c/li\u003e\u003cli\u003e 军官 $$$x$$$ 的直接上级是军官 $$$y$$$ 的下属。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e例如,在下面的图片中,军官 $$$3$$$ 的下属是:$$$5, 6, 7, 8, 9$$$。\u003c/p\u003e\u003cp\u003eBerland 军队的结构是这样组织的:除了指挥官之外的每个军官都是军队指挥官的下属。\u003c/p\u003e\u003cp\u003e形式上,让我们将 Berland 军队表示为一个包含 $$$n$$$ 个顶点的树,其中顶点 $$$u$$$ 对应于军官 $$$u$$$。顶点 $$$u$$$ 的父节点对应于军官 $$$u$$$ 的直接上级。根节点(索引为 $$$1$$$)对应于军队的指挥官。\u003c/p\u003e\u003cp\u003eBerland 战争部已经要求你回答 $$$q$$$ 个查询,第 $$$i$$$ 个查询给出为 $$$(u_i, k_i)$$$,其中 $$$u_i$$$ 是某个军官,$$$k_i$$$ 是一个正整数。\u003c/p\u003e\u003cp\u003e为了处理第 $$$i$$$ 个查询,想象一下指令是如何从 $$$u_i$$$ 传播到 $$$u_i$$$ 的下属的。这里使用了典型的 DFS(深度优先搜索)算法。\u003c/p\u003e\u003cp\u003e假设当前军官是 $$$a$$$,他传播了一个指令。军官 $$$a$$$ 选择 $$$b$$$ —— 他的一个尚未收到该指令的直接下属(即树中的子节点)。如果有很多这样的直接下属,那么 $$$a$$$ 选择索引最小的那个。军官 $$$a$$$ 给军官 $$$b$$$ 下达指令。之后,$$$b$$$ 使用完全相同的算法将指令传播到它的子树。当军官 $$$b$$$ 完成指令传播后,军官 $$$a$$$ 再次选择下一个直接下属(使用相同的策略)。当军官 $$$a$$$ 无法选择任何尚未收到该指令的直接下属时,军官 $$$a$$$ 完成指令传播。\u003c/p\u003e\u003cp\u003e让我们看一个例子:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4c032195c19c77cbe8a2e19729e00cfa?v\u003d1704303533\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e如果军官 $$$1$$$ 传播指令,军官们接收的顺序是:$$$[1, 2, 3, 5 ,6, 8, 7, 9, 4]$$$。\u003c/p\u003e\u003cp\u003e如果军官 $$$3$$$ 传播指令,军官们接收的顺序是:$$$[3, 5, 6, 8, 7, 9]$$$。\u003c/p\u003e\u003cp\u003e如果军官 $$$7$$$ 传播指令,军官们接收的顺序是:$$$[7, 9]$$$。\u003c/p\u003e\u003cp\u003e如果军官 $$$9$$$ 传播指令,军官们接收的顺序是:$$$[9]$$$。\u003c/p\u003e\u003cp\u003e为了回答第 $$$i$$$ 个查询 $$$(u_i, k_i)$$$,构造一个序列,描述如果第 $$$u_i$$$ 个军官传播指令时军官接收指令的顺序。返回构造列表中的第 $$$k_i$$$ 个元素,如果列表中的元素少于 $$$k_i$$$ 个,则返回 \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e你应该独立处理查询。一个查询不会影响其他查询。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$($$$2 \\le n \\le 2 \\cdot 10^5, 1 \\le q \\le 2 \\cdot 10^5$$$) —— Berland 军队中的军官数量和查询数量。\u003c/p\u003e\u003cp\u003e输入的第二行包含 $$$n - 1$$$ 个整数 $$$p_2, p_3, \\dots, p_n$$$($$$1 \\le p_i \u0026lt; i$$$),其中 $$$p_i$$$ 是军官索引为 $$$i$$$ 的直接上级的索引。指挥官的索引为 $$$1$$$,并且没有任何上级。\u003c/p\u003e\u003cp\u003e接下来的 $$$q$$$ 行描述了查询。第 $$$i$$$ 个查询给出为一对($$$u_i, k_i$$$)($$$1 \\le u_i, k_i \\le n$$$),其中 $$$u_i$$$ 是开始传播指令的军官的索引,$$$k_i$$$ 是指令传播序列中所需军官的索引。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出 $$$q$$$ 个数字,其中第 $$$i$$$ 个数字是描述从军官 $$$u_i$$$ 开始传播指令时军官接收指令顺序的列表中位置为 $$$k_i$$$ 的军官。如果接收指令的军官数量少于 $$$k_i$$$,则输出 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e\"。\u003c/p\u003e\u003cp\u003e你应该独立处理查询。它们不会相互影响。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9 6\n1 1 1 3 5 3 5 7\n3 1\n1 5\n3 4\n7 3\n1 8\n1 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6\n8\n-1\n9\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}