Labyrinth

题意翻译

有一个 $n$（$2 \le n \le 2 \cdot 10^5$）个点（编号为 $1,2,…,n$），$m$ （$0 \le m \le 2 \cdot 10^5$）条边的有向图，现在想找到两条路径，使得： - 它们的起点都在一个给定的点上； - 它们的终点在相同的点上（这个点可能是除起点外任意一个点）； - 它们除起点和终点外，不能有重复的点； - 每条路径不能经过重复的点。 现在给出这个图和起点，先输出是（`Possible`）否（`Impossible`）存在符合上述条件的两条路径。 如果存在，再输出： - 每条路径分别经过几个点（包括起点、终点）； - 这两条路径依次经过的点。 若不存在，不用再输出。

题目描述

Leslie and Leon entered a labyrinth. The labyrinth consists of $ n $ halls and $ m $ one-way passages between them. The halls are numbered from $ 1 $ to $ n $ . Leslie and Leon start their journey in the hall $ s $ . Right away, they quarrel and decide to explore the labyrinth separately. However, they want to meet again at the end of their journey. To help Leslie and Leon, your task is to find two different paths from the given hall $ s $ to some other hall $ t $ , such that these two paths do not share halls other than the staring hall $ s $ and the ending hall $ t $ . The hall $ t $ has not been determined yet, so you can choose any of the labyrinth's halls as $ t $ except $ s $ . Leslie's and Leon's paths do not have to be the shortest ones, but their paths must be simple, visiting any hall at most once. Also, they cannot visit any common halls except $ s $ and $ t $ during their journey, even at different times.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , and $ s $ , where $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) is the number of vertices, $ m $ ( $ 0 \le m \le 2 \cdot 10^5 $ ) is the number of edges in the labyrinth, and $ s $ ( $ 1 \le s \le n $ ) is the starting hall. Then $ m $ lines with descriptions of passages follow. Each description contains two integers $ u_i $ , $ v_i $ ( $ 1 \le u_i, v_i \le n $ ; $ u_i \neq v_i $ ), denoting a passage from the hall $ u_i $ to the hall $ v_i $ . The passages are one-way. Each tuple $ (u_i, v_i) $ is present in the input at most once. The labyrinth can contain cycles and is not necessarily connected in any way.

输出格式

If it is possible to find the desired two paths, output "Possible", otherwise output "Impossible". If the answer exists, output two path descriptions. Each description occupies two lines. The first line of the description contains an integer $ h $ ( $ 2 \le h \le n $ ) — the number of halls in a path, and the second line contains distinct integers $ w_1, w_2, \dots, w_h $ ( $ w_1 = s $ ; $ 1 \le w_j \le n $ ; $ w_h = t $ ) — the halls in the path in the order of passing. Both paths must end at the same vertex $ t $ . The paths must be different, and all intermediate halls in these paths must be distinct.

输入输出样例

输入样例 #1

5 5 1
1 2
2 3
1 4
4 3
3 5

输出样例 #1

Possible
3
1 2 3
3
1 4 3

输入样例 #2

5 5 1
1 2
2 3
3 4
2 5
5 4

输出样例 #2

Impossible

输入样例 #3

3 3 2
1 2
2 3
3 1

输出样例 #3

Impossible