玛莎将参加她就读的大学举办的才艺表演。她想用许多不同的魔术给观众留下深刻的印象!
她的其中一项技巧是使用 $$$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