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

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你正在玩一个由 $n$ 个行星组成的游戏。每个行星都有一个通向另一个行星（或自身）的传送器。

你需要处理 $q$ 个形如如下的查询：当你从行星 $x$ 出发并经过 $k$ 个传送器时，你会到达哪个行星？

输入

第一行输入包含两个整数 $n$ 和 $q$：行星数量和查询数量。行星编号为 $1,2,\dots,n$。

第二行包含 $n$ 个整数 $t_1,t_2,\dots,t_n$：对应每个行星，传送器的目的地。有可能 $t_i=i$。

最后有 $q$ 行描述查询。每行包含两个整数 $x$ 和 $k$：你从行星 $x$ 出发，经过 $k$ 个传送器。

输出

输出每个查询的答案。

数据范围

$1 \le n, q \le 2 \cdot 10^5$ $1 \le t_i \le n$ $1 \le x \le n$ $0 \le k \le 10^9$

样例输入

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

样例输出

1
2
4