Zadanie PPR8
Treść
Dany jest graf oraz dwa jego wierzchołki. Znajdź liczbę krawędzi w najkrótszej ścieżce
łączącej te dwa wierzchołki, lub stwierdź, że ścieżka taka nie istnieje.
Specyfikacja wejścia
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 <= D <= 50), oznaczają liczbę zestawów danych.
W pierwszej linii zestawu znajdują się dwie liczby naturalne n i m (1<=n<=5000, 0<=m<=
50000) oznaczające odpowiednio liczbę wierzchołków oraz liczbę krawędzi w grafie.
Kolajnych m linii zawiera pary liczb z przedziału od 1 do n, które oznaczają krawędzie
znajdujące się w grafie. W ostatniej linii zestawu znajdują się dwie liczby naturalne x i
y (1<=x,y<=n) oznaczające numery wierzchołków pomiędzy którymi szukać będziemy połączenia.
Specyfikacja wyjścia
Na wyjściu należy dla każdego zestawu danych wypisać w osobnej linii liczbę krawędzi w
najkrótszej ścieżke łączącej te dwa wierzchołki, lub "niesk" jeśli połączenie takie nie istnieje.
Przykład
Wejście
3
3 3
1 2
2 3
3 1
1 2
7 9
1 2
2 3
3 4
4 1
1 3
2 4
6 7
7 5
6 5
1 5
5 5
1 2
2 3
3 4
4 5
1 3
1 5
Wyjście
1
niesk
3