Training Site

# 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