Egy állatkertben ismerjük a bejárható útvonalakat. A bejárat a 0-s sorszámú pont. Az egyes állatokat az 1 és N közötti sorszámukkal azonosítjuk, az utakat pedig két olyan állat sorszámával, amelyek ketrece között vezetnek. A látogatók szeretnének bizonyos állatokhoz a lehető legrövidebb úton eljutni.

Írjunk programot, ami az állatkerti utak ismeretében megadja, hogy a bejárattól melyik állathoz hányféleképpen lehet a lehető legrövidebb úton eljutni.

A bemenet első sorában az állatok N száma (1<= N <= 40) és az utak M száma (1 <= M <= 1000) van. A következő M sorban egy-egy út leírása található: azon két állat sorszáma, amelyek között az út vezet.

N sort kell kiírni. Az i-dik sorba a bejárattól az i sorszámú állathoz vezető legrövidebb utak száma kerüljön!

Bemenet	Kimenet
5 7 0 1 1 4 3 1 3 5 2 0 2 3 4 5	1 1 2 1 3

A feladat forrása: NTOITV 9-10. évfolyam, 2012 3. forduló

Algoritmusok: gráfbejárás

megoldás