CF1666L.Labyrinth

Leslie 和 Leon 进入了一个迷宫。迷宫由 $n$ 个大厅和 $m$ 条单向通道组成。大厅编号为 $1$ 到 $n$。

Leslie 和 Leon 从大厅 $s$ 开始他们的旅程。很快，他们发生了争吵，决定分开探索迷宫。然而，他们希望在旅程结束时再次相遇。

为了帮助 Leslie 和 Leon，你的任务是从给定的大厅 $s$ 出发，找到两条到某个大厅 $t$ 的不同路径，使得这两条路径除了起点 $s$ 和终点 $t$ 外，不经过任何相同的大厅。大厅 $t$ 尚未确定，你可以选择除 $s$ 以外的任意一个大厅作为 $t$。

Leslie 和 Leon 的路径不要求是最短路径，但每条路径必须是简单路径，即每个大厅最多只能经过一次。此外，他们在旅途中，除了 $s$ 和 $t$ 外，不能在任何时刻经过相同的大厅。

第一行包含三个整数 $n$、$m$ 和 $s$，其中 $n$（$2 \le n \le 2 \cdot 10^5$）表示大厅的数量，$m$（$0 \le m \le 2 \cdot 10^5$）表示迷宫中的通道数量，$s$（$1 \le s \le n$）表示起始大厅的编号。

接下来的 $m$ 行，每行描述一条通道。每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \neq v_i$），表示一条从大厅 $u_i$ 到大厅 $v_i$ 的单向通道。每个通道 $(u_i, v_i)$ 在输入中最多出现一次。迷宫中可能存在环，也不一定是连通的。

如果可以找到满足条件的两条路径，输出 "Possible"，否则输出 "Impossible"。

如果存在答案，接下来输出两条路径的描述。每条路径的描述占两行。第一行包含一个整数 $h$（$2 \le h \le n$），表示路径经过的大厅数，第二行包含 $h$ 个互不相同的整数 $w_1, w_2, \dots, w_h$（$w_1 = s$；$1 \le w_j \le n$；$w_h = t$），表示路径经过的大厅编号顺序。两条路径必须以同一个大厅 $t$ 结束。两条路径必须不同，并且两条路径中所有中间经过的大厅必须互不相同。

由 ChatGPT 4.1 翻译