Dynamit

Limit pamięci: 64 MB

Jaskinia Bajtocka składa się z komór oraz z łączących je korytarzy. Nie wychodząc z jaskini, pomiędzy każdą parą komór można przejść bez zawracania na dokładnie jeden sposób. W niektórych komorach pozostawiono dynamit. Wzdłuż każdego korytarza rozciągnięto lont. W każdej komorze wszystkie lonty z prowadzących do niej korytarzy są połączone, a jeżeli w danej komorze znajduje się dynamit, to jest on połączony z lontem. Lont biegnący korytarzem pomiędzy sąsiednimi komorami spala się w jednej jednostce czasu, a dynamit wybucha dokładnie w chwili, gdy ogień znajdzie się w komorze zawierającej ten dynamit.

Chcielibyśmy równocześnie podpalić lonty w jakichś komorach (w miejscu połączenia lontów) w taki sposób, aby wszystkie ładunki dynamitu wybuchły w jak najkrótszym czasie, licząc od momentu podpalenia lontów. Napisz program, który wyznaczy najkrótszy możliwy taki czas.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę komór w jaskini oraz liczbę komór, w których możemy podpalić lonty. Komory są ponumerowane od 1 do . Kolejny wiersz zawiera liczb całkowitych (), pooddzielanych pojedynczymi odstępami. Jeśli , to w -tej komorze znajduje się dynamit, a jeśli , to nie ma w niej dynamitu. Kolejne wierszy opisuje korytarze w jaskini. W każdym z nich znajdują się dwie liczby całkowite () oddzielone pojedynczym odstępem i oznaczające, że istnieje korytarz łączący komory i . Każdy korytarz pojawia się w opisie dokładnie raz.

Możesz założyć, że w testach wartych łącznie 10\% punktów zachodzi dodatkowy warunek , a w testach wartych łącznie 40\% punktów zachodzi .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnemu czasowi od podpalenia lontów, po jakim wybuchną wszystkie ładunki dynamitu.

Przykład

Dla danych wejściowych:

7 2
1 0 1 1 0 1 1
1 3
2 3
3 4
4 5
5 6
5 7

poprawną odpowiedzią jest:

1

Wyjaśnienie do przykładu: Podpalamy lonty w komorach 3 i 5. W chwili zero wybucha dynamit w komorze 3, a po jednostce czasu zapalone zostają dynamity w komorach 1, 4, 6 i 7.

Autor zadania: Jacek Tomasiewicz.