#T2149. 公司查询 I(Company Queries I)

公司查询 I(Company Queries I)

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

板块: Tree Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

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

你需要处理 qq 次查询,形式为:员工 xx 在层级中向上第 kk 层的上司是谁?

输入

第一行包含两个正整数 nn 和 qq:员工数和查询数。员工编号为 1,2,…,n1,2,\dots,n,且员工 11 是总经理。

下一行有 n−1n-1 个整数 e2,e3,…,ene_2,e_3,\dots,e_n:分别给出员工 2,3,…,n2,3,\dots,n 的上司。

最后有 qq 行描述查询。每行包含两个正整数 xx 和 kk:员工 xx 向上第 kk 层的上司是谁?

输出

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

数据范围

1≤n,q≤2⋅1051 \le n,q \le 2 \cdot 10^5 1≤ei≤i−11 \le e_i \le i-1 1≤x≤n1 \le x \le n 1≤k≤n1 \le k \le n

样例输入

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

样例输出

3
1
-1