Shortest path P81453


Statement
 

pdf   zip

thehtml

Write a program that, given a directed graph with n vertices (numbered from 0 to n−1) and m arcs, prints the shortest way to go from 0 to n−1.

Input

Input consists of several cases. Every case begins with n and m. Follow m pairs x y to indicate an arc from x to y. There are no repeated arcs nor of the kind x x. There is always a path between 0 and n−1. You can assume 2 ≤ n ≤ 104 and 1 ≤ m ≤ 5n.

Output

For every case, print the vertices of the shortest path between 0 and n−1 separated by spaces. If there is more than one shortest path, print the smallest in lexicographical order.

Public test cases
  • Input

    10 11
    8 2  0 1  4 0  1 4  3 9  4 6
    6 9  0 8  2 9  0 7  7 3
    
    2 2
    1 0  0 1
    

    Output

    0 7 3 9
    0 1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++