解题思路

这题本质上是一个树上第 $k$ 级祖先查询问题。

已知：

• 第 $2$ 到第 $n$ 号生物的父亲编号
• $1$ 号生物的父亲不存在
• 每次查询给出 $x,k$，要求第 $x$ 号生物的第 $k$ 级祖先

题目内容

你的实验室中诞生了一种新的无性繁殖生物，这种生物每一个都有唯一的父亲(注意，其中有且仅有$1$号生物的父亲无法追踪到了)。为了研究方便，你定义一个生物的$1$级祖先即为其父亲，而其$k$级祖先为$k-1$级祖先的父亲$(k≥2)$。例如，$2$级祖先即为父亲的父亲。现在你想知道一些生物的若干级父亲。

$n,q≤50000$， $1≤a<i$，$1≤x, k≤n$

输入描述

第一行两个以空格隔开的正整数$n$和$q$。表示生物总数和询问次数

第二行有$n-1$个由空格隔开的正整数，$a_2,a_3,...a_n$，依次表示$2$号生物的父亲、$3$号生物的父亲....$i$号生物的父亲的编号为$a_i$。其中$1$号生物的父亲已经无法追踪到了。

接下来$q$行，每行两个由空格隔开的正整数$x,k$，表示询问第$x$号生物的$k$级祖先。

输出描述

输出$q$行，每行依次对应一个询问的答案，即第$x$号生物的$k$级祖先。如果无法追踪到该祖先，则输出$0$

样例1

输入

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

输出

4
0 
2

说明

第二次询问$1$号节点的$1$级祖先，即父亲，但$1$号节点的父亲已经无法追踪了，因而输出$0$