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* ≤ 10^{4} and 1 ≤ *m* ≤ 5*n*.

**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++