莱斯利和莱昂进入了一个迷宫。迷宫由 $$$n$$$ 大厅和大厅之间的 $$$m$$$ 单向通道组成。大厅编号从 $$$1$$$ 到 $$$n$$$。
Leslie 和 Leon 在大厅 $$$s$$$ 开始他们的旅程。他们立即发生争吵并决定单独探索迷宫。然而,他们想在旅程的终点再次见面。
为了帮助Leslie和Leon,你的任务是找到从给定大厅$$$s$$$到其他大厅$$$t$$$的两条不同路径,使得这两条路径不共享除了起始大厅$$$s$$$和结束大厅$$$t$$$之外的大厅。大厅$$$t$$$尚未确定,因此您可以选择迷宫的任何大厅作为$$$t$$$,除了$$$s$$$。
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)$$$ 在输入中最多出现一次。迷宫可以包含循环,并且不一定以任何方式连接。
输出
如果可以找到所需的两条路径,则输出“可能“,否则输出”不可能".
如果答案存在,则输出两个路径描述。每个描述占据两行。描述的第一行包含一个整数 $$$h$$$ ($$$2 \le h \le n$$$) — 路径中大厅的数量,第二行包含不同的整数 $$$w_1, w_2, \dots, w_h$$$ ($$$w_1 = s$$$; $$$1 \le w_j \le n$$$; $$$w_h = t$$$) —路径中的大厅按经过的顺序排列。两条路径必须在同一顶点 $$$t$$$ 处结束。路径必须是不同的,并且这些路径中的所有中间大厅必须是不同的。
示例
输入复制
5 5 1 1 2 2 3 1 4 4 3 3 5
输出复制
Possible 3 1 2 3 3 1 4 3
输入复制
5 5 1 1 2 2 3 3 4 2 5 5 4
输出复制
Impossible
输入复制
3 3 2 1 2 2 3 3 1
输出复制
Impossible