Camí més curt P81453

Feu un programa que, donat un graf dirigit amb n vèrtexs (numerats entre 0 i n−1) i m arcs, escrigui el camí més curt per anar de 0 a n−1.

Entrada

L’entrada consisteix en diversos casos. Cadascun comença amb n i m. Segueixen m parells x y indicant un arc de x a y. No hi ha arcs repetits ni del tipus x x. Sempre hi ha algun camí entre 0 i n−1. Podeu suposar 2 ≤ n ≤ 10⁴ i 1 ≤ m ≤ 5n.

Sortida

Per a cada cas, escriviu els vèrtexs del camí més curt entre 0 i n−1 separats amb espais. Si hi ha més d’un camí mínim, escriviu el més petit en ordre lexicogràfic.