题目描述

给你一棵树，树上有 $n$ 个节点，按从 $0$ 到 $n-1$ 编号。树以父节点数组的形式给出，其中 $parent[i]$ 是节点 $i$ 的父节点。树的根节点是编号为 $0$ 的节点。

树节点的第 $k$ 个祖先节点是从该节点到根节点路径上的第 $k$ 个节点。

输入格式

第一行两个空格隔开的整数，分别表示节点个数$n$ 和 查询次数 $m$；

第二行 $n$ 个空格隔开的整数，分别表示节点 $i(1\le i \lt n)$ 的父亲节点编号， -1 表示根节点没有父亲结点；

接下来 $m$ 行，每行两个整数，表示要节点 $node$ 的第 $k$ 个祖先节点。

输出格式

一行一个整数表示节点 $node$ 的第 $k$ 个祖先节点。如果不存在这样的祖先节点，输出 $-1$ 。。

示例 1：

7 3
-1 0 0 1 1 2 2
3 1
5 2
6 3

1
0
-1

提示：

• $1 <= k <= n <= 5 * 10^4$
• $parent[0] == -1$ 表示编号为 $0$ 的节点是根节点。
• 对于所有的 $0 < i < n$ ，$0 <= parent[i] < n$ 总成立
• $0 <= node < n$
• 至多查询 $5 * 10^4$ 次

SOURCE

1483. 树节点的第 K 个祖先