Problem
Znalezienie najkrótszej drogi z wierzchołka s do wierzchołka v w danym grafie niezorientowanym.
Wejście
W pierwszej linii liczba naturalna 0 < n <= 100 = liczba wierzchołków grafu (wierzchołki numerujemy kolejnymi liczbami naturalnymi 0,1,...n-1).
W drugiej linii liczba naturalna 0 <= m = liczba krawędzi grafu.
W kolejnych m liniach kolejne krawędzie w postaci par liczb z przedziału [0,n-1].
W ostatniej linii para liczb s,v z przedziału [0,n-1].
Wyjście - dwie możliwości
(1) Gdy istnieje w grafie droga z s do v, na wyjściu powinna się pojawić najkrótsza droga z s do v w formie serii numerów wierzchołków od s do v (w jednej linii, oddzielone spacjami).
(2) W przeciwnym wypadku napis 'nie ma drogi'.
Wskazówki
(1) Wczytaj graf jako tablicę list sąsiedztwa.
(2) Użyj przeglądania grafu wszerz.
Przykładowe wejście I
8
7
0 1
2 3
0 2
2 1
3 4
4 5
6 7
0 5
Wynik I
0 2 3 4 5
Przykładowe wejście II
8
7
0 1
2 3
0 2
2 1
3 4
4 5
6 7
0 7
Wynik II
nie ma drogi