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 \le n \le 10^4$ i $1 \le m \le 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.