AT_abc030_d.[ABC030D] へんてこ辞書

ミカミ君正在使用一本可疑的英语单词本。这本单词本中包含了 $N$ 个单词的释义，对于第 $i$ 个单词的解释，仅仅写着“与单词 $b_i$ 意思相同”。这里，我们将第 $i$ 个单词称为单词 $i$。

由于ミカミ君还一个英语单词都不认识，所以当他想要查找单词 $i$ 的意思时，他会去查找单词 $b_i$ 的意思。ミカミ君很认真，即使之前已经查过的单词，他也会继续按照同样的方法查找。

然而遗憾的是，这本单词本中并没有写明任何单词的实际含义，因此他始终无法得知单词的真正意思。

每当ミカミ君尝试查找某个单词 $i$，并根据单词本去查找单词 $b_i$ 时，记为一步操作。

请问，当ミカミ君从单词 $a$ 开始查找，经过 $k$ 步操作后，他正在查找的是哪一个单词？

输入通过标准输入给出，格式如下：

$N$ $a$

$k$

$b_1$ $b_2$ … $b_N$

• 第 $1$ 行包含两个用空格分隔的整数，分别表示单词的数量 $N\ (2 \leq N \leq 10^5)$ 和ミカミ君最初要查找的单词编号 $a\ (1 \leq a \leq N)$。
• 第 $2$ 行包含一个整数 $k\ (1 \leq k \leq 10^{100000})$，表示查找的步数。
• 第 $3$ 行包含 $N$ 个用空格分隔的整数 $b_1, b_2, \ldots, b_N$，表示每个单词的解释。
• 保证 $1 \leq b_i \leq N$ 且 $b_i \neq i\ (1 \leq i \leq N)$。

输出ミカミ君从单词 $a$ 开始查找，经过 $k$ 步操作后，正在查找的单词编号。输出应为一行，并以换行符结尾。

部分分

本题设置了部分分。

• 若能正确解决 $k \leq 10^{18}$ 的数据集，则可获得 $50$ 分。

样例解释 1

ミカミ君在每一步的查找过程如下：

第 $1$ 步，为了查找单词 $4$ 的意思，去查找单词 $2$。

第 $2$ 步，为了查找单词 $2$ 的意思，去查找单词 $3$。

第 $3$ 步，为了查找单词 $3$ 的意思，去查找单词 $1$。

第 $4$ 步，为了查找单词 $1$ 的意思，去查找单词 $2$。

第 $5$ 步，为了查找单词 $2$ 的意思，去查找单词 $3$。

因此，经过 $5$ 步后，ミカミ君正在查找单词 $3$。

样例解释 2

$k$ 可能会非常大。

由 ChatGPT 4.1 翻译