Agenci
Limit pamięci: 32 MB
W związku z ostatnimi wpadkami swoich agentów,
Urząd Ochrony Bajtocji postanowił usprawnić działalność.
Największym dotychczasowym problemem było bezpieczne
urządzanie spotkań agentów.
Twój program ma pomóc w rozwiązaniu tego problemu.
Dla podanego opisu sieci dróg Bajtocji oraz początkowej pozycji dwóch
agentów powinien stwierdzać czy możliwe jest bezpieczne spotkanie
dwóch agentów.
Żeby spotkanie uznać za bezpieczne agenci muszą przestrzegać
następujących reguł:
-
agenci poruszają się w dzień, natomiast spotkania odbywają się
wieczorami,
-
każdego dnia agent musi zmienić miejsce pobytu,
-
agenci mogą poruszać się jedynie po drogach łączących miasta
(niestety dodatkowym utrudnieniem jest fakt, iż w Bajtocji
drogi są jednokierunkowe),
-
agent nie może jednak poruszać się zbyt szybko (mogło by to wzbudzać
niepotrzebne zainteresowanie) - jednego dnia nie może przemieścić
się dalej niż do sąsiedniego miasta,
-
odległość między dwoma miastami połączonymi drogą jest na tyle
mała, że agent wyruszający z pierwszego miasta zawsze
dotrze do drugiego miasta przed wieczorem,
-
spotkanie uznaje się za odbyte w momencie, gdy dwaj
agenci znajdą się tego samego wieczora w tym samym mieście.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia liczbę miast i opis sieci
dróg Bajtocji, oraz pozycje początkowe dwóch agentów,
-
stwierdzi, czy możliwe jest ich bezpieczne spotkanie,
a jeśli tak, to po ilu dniach,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby
całkowite i , oddzielone pojedynczym odstępem,
gdzie , .
W drugim wierszu znajdują się dwie liczby całkowite i
oddzielone pojedynczym odstępem,
oraz ,
oznaczające odpowiednio początkowe pozycje agentów nr 1 i nr 2.
W następnych wierszach znajdują się pary liczb naturalnych i
oddzielone pojedynczymi odstępami,
oraz ,
oznaczające istnienie drogi z miasta do miasta .
Wyjście
Standardowe wyjście powinno zawierać dokładnie wiersz
zawierający:
-
dokładnie jedną dodatnią liczbę całkowitą , oznaczającą minimalny
czas (w dniach) potrzebny do zorganizowania bezpiecznego spotkania
dwóch agentów - jeżeli do takiego spotkania można doprowadzić,
-
słowo NIE, gdy nie można doprowadzić do bezpiecznego spotkania.
Przykład
Dla danych wejściowych:
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
poprawną odpowiedzią jest:
3
Autor zadania: Tomasz Waleń.