读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE。

输入：command.in

输出：command.out

题目描述

伯兰国军队共有 $n$ 名军官，编号为 $1\sim n$。其中 $1$ 号是总司令，没有上级；其余每名军官都有且仅有一个直属上级。于是整支军队可以看作一棵以 $1$ 为根的树。

下图给出了一个军队结构示意：

现在要模拟“命令下发”过程：当某名军官开始下发命令时，他会先把命令传给自己所有还没收到命令的直属下属，传递顺序按编号从小到大。每传给一个下属后，该下属会立刻用同样规则向自己的子树继续传递，直到完成后再回到当前军官处理下一个下属。这一过程等价于“按子节点编号升序进行 DFS 先序遍历”。

给定 $q$ 次询问，每次给出 $(u,k)$：

• 设命令从军官 $u$ 开始下发；
• 记下发顺序形成的序列；
• 输出该序列的第 $k$ 个军官编号；若不存在则输出 $-1$。

各询问相互独立。

输入格式

第一行两个整数 $n,q$（$2 \le n \le 2\times 10^5,\ 1 \le q \le 2\times 10^5$）。

第二行给出 $n-1$ 个整数 $p_2,p_3,\dots,p_n$（$1 \le p_i < i$），其中 $p_i$ 表示军官 $i$ 的直属上级编号。

接下来 $q$ 行，每行两个整数 $u,k$（$1 \le u,k \le n$），表示一次询问。

输出格式

输出 $q$ 行。对于每个询问输出对应答案。

输入输出样例

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

说明/提示

在样例中，若从军官 $1$ 开始下发，顺序为：$[1,2,3,5,6,8,7,9,4]$。