← 返回题目列表

Codeforces · 1346/E

E. 魔术

中文机器翻译题面 查看原题

玛莎将参加她就读的大学举办的才艺表演。她想用许多不同的魔术给观众留下深刻的印象!

她的其中一项技巧是使用 $$$n$$$ 海绵球,其中一个是特殊的。首先,她将球排成一排,将特殊球放在 $$$k$$$ 位置(位置从左到右编号为 $$$1$$$ 到 $$$n$$$)。之后,她执行 $$$m$$$ 交换:在第 $$$i$$$ 交换期间,她选择位置 $$$x_i$$$ 上的球和位置 $$$y_i$$$ 上的球,然后交换它们。

由于玛莎是一名魔术师,她会伪造一些动作来欺骗观众——当她开始表演交换时,她可能会伪造,因此不会表演(但看起来像是为观众表演的)。对于玛莎应该伪造或实际执行哪些交换没有任何限制——例如,她可以伪造所有交换,甚至根本不伪造任何内容。

为了让这个技巧完美地发挥作用,特殊的球应该结束在一个特定的位置——玛莎还没有决定哪个位置是完美的。由于伪造交换很困难,因此对于每个位置,她想知道她必须伪造的最小交换次数,以便特殊球最终到达那里。

不幸的是,玛莎是一名魔术师,既不是数学家,也不是程序员。所以她需要你的帮助来计算她想要什么!

输入

第一行包含三个整数 $$$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$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) 表示第 $$$i$$$ 交换。

输出

打印 $$$n$$$ 整数。第 $$$i$$$ 个整数应该是 Masha 必须伪造的最小交换次数,以便特殊球最终位于 $$$i$$$ 位置(或 $$$-1$$$,如果 Masha 无法将特殊球放在那里)。

示例

输入 #1

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

输出 #1

2 0 3 1

输入 #2

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

输出 #2

2 2 0 3 1

输入 #3

7 15 5
5 3
4 2
6 1
2 4
1 6
3 7
5 6
4 2
6 4
2 6
6 3
6 3
7 6
2 6
7 2

输出 #3

-1 1 1 1 2 1 0