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.