P12825 [NERC 2021] 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$，且路径必须不同，所有中间大厅必须互不相同。

翻译由 DeepSeek V3 完成