Labyrinth

Description:

Input:

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.

Output:

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.

Sample Input:

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

Sample Output:

Possible
3
1 2 3
3
1 4 3

Sample Input:

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

Sample Output:

Impossible

Sample Input:

3 3 2
1 2
2 3
3 1

Sample Output:

Impossible