Training Site
Sideways banner

Shortest Path

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 2.0 seconds

Read in a directed graph which has been described as a list of edges, a source and a destination vertex and then output the shortest path between the source and the destination.

An extra rule so that your results can be easily compared:
At any point if there is a choice of which vertex to visit, visit them in ascending numerical order

Eg: if a vertex's neighbours are 5,2,7 and 3 process them in the order 2, 3, 5 then 7.

Input format

Each vertex will be represented as a number from 0 to n-1 for n vertices.
The first line of input will state how many vertices are in the graph
The second line will specify the start and destination vertices
Each subsequent line will consist of pairs of numbers each describing an edge. The first number in the pair describes the vertex from where the edge originates and the second number states the vertex where the edge leads to.
The list will end with the end of the file.

Output format

Output the shortest path from the source to the destination as a list of vertices, on one line, separated by spaces.

Bounds

1 <= n <= 1,000,000 and 0 <= total number of edges <= 1,000,000

Sample Input 1

3
2 1
0 1
1 0
1 2
0 2
2 0

Sample Output 1

2 0 1

Sample Input 2

10
5 5
1 2
2 3

Sample Output 2

5