Ż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

6 5
1 2
2 3
2 4
4 5
4 6
3
2
5
6

1

Autor zadania: Jakub Radoszewski.