Dungeon

Now that we have saved Faust and Mephistopheles (and Gretchen) from the dungeon, let us consider how they got them into the fix in the first place. Obviously, running into the dungeon with no plan could have gotten them stuck behind a wall of guards, so let us step back and plan both routes.

Faust and Mephistopheles visit the dungeon gift shop, and pick out a detailed map, including all hallways and cells and the positions of every posted guard. Using this map, they must plot a path to reach Gretchen's cell and free her.

But wait! They will have to rush past the guards at the entrance of the dungeon, so will be followed. Staying ahead of the guards is no problem, but there are enough entrance guards to post one at every intersection and cell behind them.

Before starting the rescue, Faust and Mephistopheles will have to find a route they can take into the dungeon, past unguarded intersections and cells to Gretchen's cell, and then back to the entrance through a still unguarded route. (The guards at the entrace are expected to chase them into the dungeon, so they will also use it as their exit.)

Input Specification

Locations on the map are represented by integers. Intersections range from 1 to 5000, cells from 5001 to 10000, and the entrance/exit is 0.

The input starts with two numbers in a line: the number of intersections and the number of cells. This is followed by a line containing Gretchen's cell number, G. Then comes the list of hallways that are not yet guarded (no guard at either end) as two integers on each line. The list ends with the pair “0 0”.

No more than 2000 intersections or cells will be reachable from the entrance. No more than 2000 unique paths from entrance to target will exists. No more than 2500 connections will be specified in the input.

Output Specification

The output contains the list of locations to be visited by Faust and Mephistopheles during their rescue, as one integer per line, starting and ending with 0. There will always be at least one valid route, any of which will be accepted.

Sample Input

1. 4 3
2. 5002
3. 0 1
4. 1 2
5. 2 3
6. 2 4
7. 3 4
8. 4 0
9. 1 5001
10. 2 5001
11. 2 5002
12. 3 5002
13. 3 5003
14. 4 5003
15. 0 0

download as text file

Output for Sample Input

1. 0
2. 1
3. 2
4. 5002
5. 3
6. 4
7. 0

download as text file