AT_arc056_b.[ARC056B] 駐車場

有 $N$ 个人想要在停车场停车。停车场有 $N$ 个停车位，编号从 $1$ 到 $N$。此外，有 $M$ 条双向道路，每条道路连接两个停车位，第 $i$ 条道路连接第 $u_i$ 个停车位和第 $v_i$ 个停车位。停车位 $S$ 与停车场的入口相连。

第 $i$ 个人只想把车停在第 $i$ 个停车位。因此，如果从停车场入口出发，无法通过尚未被占用的停车位和道路到达第 $i$ 个停车位时，第 $i$ 个人就会直接离开，不停车。

第 $1$ 个人到第 $N$ 个人依次来到停车场。请按升序输出最终能够停车的人的编号，每行输出一个编号。

输入以如下格式从标准输入读入。

$N$ $M$ $S$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

请按升序输出最终能够停车的人的编号，每行输出一个编号。

限制条件

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $1 \leq S \leq N$
• 从入口出发，经过道路和停车位可以到达所有停车位

部分得分

• 如果能通过 $M \leq 2,000$ 的所有测试用例，将获得部分分 $40$ 分。

样例解释 1

第 $1$ 辆车可以到达停车位 $1$，因此停在那里。第 $2$ 辆车可以到达停车位 $2$，因此停在那里。第 $3$ 辆车由于第 $2$ 辆车已经占用了停车位 $2$，无法到达停车位 $3$，因此离开。

样例解释 2

蓝色圆圈表示空闲的停车位，红色圆圈表示已被占用的停车位。停车位会按照上图的顺序被依次占用，第 $4$ 辆车无法停车。

由 ChatGPT 4.1 翻译