Escape

Faust and Mephistopheles have gone into the dungeon to free Gretchen. After rushing past the guards at the gate and winding their way through the dungeons, they arrive at Gretchen's cell. On the wall beside the cell is a detailed map of the dungeon, including all hallways and cells and the positions of every guard. Using this map, they must plot a path to return to the entrance and escape.

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”.

Output Specification

The output contains the list of locations to be visited by Faust and Mephistopheles during their escape, as one integer per line, starting with Gretchen's cell 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. 5002
2. 3
3. 4
4. 0

download as text file