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ń.