Planets Queries I

题目描述

你在玩一个由 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 次传送器。

输出格式

对每个查询输出答案。

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

1
2
4

提示

$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$

标签: CSES1750|图论

来源

CSES1750|图论