CF1346E Magic Tricks

Masha 即将在她所在大学举办的才艺表演中登台表演。她想用许多不同的魔术把观众惊艳到！ 在其中一个魔术中，她使用了 $n$ 个海绵球，其中有一个是特殊的。首先，她将这些球排成一行，并把特殊的球放在第 $k$ 个位置（位置从左到右编号为 $1$ 到 $n$）。接着，她会进行 $m$ 次交换：在第 $i$ 次交换时，她选择第 $x_i$ 个位置的球和第 $y_i$ 个位置的球，并交换它们。 由于 Masha 是一名魔术师，她会假装进行一些交换来迷惑观众——也就是说，她可以选择某些交换实际上并不执行（但观众看起来像是执行了）。对于哪些交换需要假装、哪些需要真正执行，没有任何限制——例如，她可以假装所有的交换，或者全部都真实执行。 为了让魔术表演得完美，特殊的球最终应该出现在某个特定的位置——但 Masha 还没有决定哪个位置最合适。由于假装交换很难，对于每一个位置，她都想知道，最少需要假装多少次交换，才能让特殊的球最终出现在该位置。 不幸的是，Masha 是一名魔术师，而不是数学家或程序员。因此她需要你的帮助来计算她想要的结果！

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$1 \le m \le 2 \cdot 10^5$；$1 \le k \le n$），分别表示球的数量、交换的次数以及特殊球的初始位置。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$；$x_i \ne y_i$），表示第 $i$ 次交换涉及的位置。

输出 $n$ 个整数。第 $i$ 个整数表示，为了让特殊的球最终出现在第 $i$ 个位置，Masha 至少需要假装多少次交换（如果无法让特殊球到达该位置，则输出 $-1$）。

由 ChatGPT 4.1 翻译