Training Site
Sideways banner

Solving a Maze I

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

Solving a maze

Find your way out of a maze

The maze is constructed of a series of numbered rooms. Two rooms are special, 0 is the entrance of the maze and the room with the highest number is the exit of the maze.

Input

The maze is represented by a single line specifying how many rooms are in the maze followed by lines of pairs of numbers until the end of the file. Each pair represents a door between the two rooms.

Output

Write a list of the rooms that an adventurer should walk through in order to walk from the entrance to the exit in the shortest possible way.

  • Sample Input 1

    34
    1 2
    2 3
    3 4
    4 5
    0 6
    7 8
    9 10
    10 11
    13 14
    14 15
    15 16
    17 18
    18 19
    22 23
    26 33
    27 28
    28 29
    29 30
    30 31
    31 32
    1 6
    6 9
    17 21
    21 24
    24 27
    11 13
    13 19
    25 29
    5 7
    7 12
    12 15
    15 20
    20 23
    26 32
    

    Sample Output 1

    0 6 9 10 11 13 19 18 17 21 24 27 28 29 30 31 32 26 33