链接: https://cses.fi/problemset/task/1687

板块: Tree Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一家公司拥有 $n$ 名员工，构成树形层级结构，其中除总经理外每位员工都有一位上司。

你需要处理 $q$ 次查询，形式为：员工 $x$ 在层级中向上第 $k$ 层的上司是谁？

输入

第一行包含两个正整数 $n$ 和 $q$：员工数和查询数。员工编号为 $1,2,\dots,n$，且员工 $1$ 是总经理。

下一行有 $n-1$ 个整数 $e_2,e_3,\dots,e_n$：分别给出员工 $2,3,\dots,n$ 的上司。

最后有 $q$ 行描述查询。每行包含两个正整数 $x$ 和 $k$：员工 $x$ 向上第 $k$ 层的上司是谁？

输出

对每个查询输出答案。若不存在这样的上司，输出 $-1$。

数据范围

$1 \le n,q \le 2 \cdot 10^5$ $1 \le e_i \le i-1$ $1 \le x \le n$ $1 \le k \le n$

样例输入

5 3
1 1 3 3
4 1
4 2
4 3

样例输出

3
1
-1