Żuczki
Limit pamięci: 32 MB
W Tajemniczej Krainie Żuczków znajduje się wiele domków.
Nie wszystkie domki są zamieszkałe. Wiadomo jednak,
że w każdym domku mieszka co najwyżej jeden żuczek.
Pewne pary różnych domków są połączone ścieżkami.
Między dowolną parą różnych domków istnieje dokładnie
jedna trasa złożona ze ścieżek taka, że żadna ścieżka się
na niej nie powtarza.
Pewnego dnia wszystkie żuczki postanowiły się spotkać w jednym domku, gdyż
czeka je narada w sprawie przyszłości ich Tajemniczej Krainy (ale to jest
tajemnica!).
Umówiły się więc, że co godzinę każdy żuczek wyruszy
pewną ścieżką wychodzącą z domku, przy którym aktualnie się
znajduje i dojdzie nią do przeciwległego domku na tej ścieżce (przejście dowolną ścieżką
w Tajemniczej Krainie Żuczków zajmuje dowolnemu żuczkowi dokładnie jedną
godzinę).
Żuczki zamierzają wykonywać tę procedurę do chwili, gdy
spotkają się wszystkie przy tym samym domku (będą przy nim dokładnie w tym samym momencie).
Niestety żuczki nie
przewidziały, że spotkanie się przy takiej metodzie
przechodzenia może być dość czasochłonne, albo wręcz niemożliwe.
Dlatego (oczywiście w tajemnicy) poprosiły Ciebie o pomoc w sprawdzeniu,
czy mogą się spotkać, a jeżeli tak, to w jakim najkrótszym czasie mogą
to uczynić.
Zadanie
Napisz program, który:
- wczyta opis Tajemniczej Krainy Żuczków,
- sprawdzi, czy żuczki mogą się spotkać, poruszając się zgodnie z obraną procedurą,
a jeżeli tak, to wyznaczy
najkrótszy czas potrzebny im na dotarcie do miejsca spotkania,
- wypisze wynik.
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite oraz
(, ),
oddzielone pojedynczym odstępem i
oznaczające odpowiednio liczbę domków i liczbę ścieżek w Tajemniczej Krainie.
Domki są ponumerowane liczbami całkowitymi od do . W następnych
wierszach znajdują się opisy ścieżek. Każdy z nich składa się z
dwóch liczb całkowitych oraz (), oddzielonych
pojedynczym odstępem i oznaczających numery domków, które łączy
dana ścieżka. Następny wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę żuczków mieszkających w Tajemniczej
Krainie. Każdy z następnych wierszy zawiera jedną liczbę całkowitą
(), która oznacza numer domku, w którym mieszka
dany żuczek.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać albo jedno słowo NIE, jeżeli
żuczki nie mogą się spotkać poruszając się zgodnie z obraną procedurą, albo jedną
liczbę całkowitą, równą liczbie godzin potrzebnych na dotarcie wszystkich
żuczków do punktu spotkania.
Przykład
Dla danych wejściowych:
6 5
1 2
2 3
2 4
4 5
4 6
3
2
5
6
poprawną odpowiedzią jest:
1
Autor zadania: Jakub Radoszewski.