W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W stolicy jest skrzyżowań oraz dróg je łączących. Sieć dróg jest taka, że z każdego skrzyżowania da się dojechać do każdego innego w dokładnie jeden sposób. Przy niektórych skrzyżowaniach znajdują się chińskie bary, zwane chińczykami.
Kozik chce zamieszkać w stolicy. W tym celu chce wybrać mieszkanie znajdujące się przy pewnym skrzyżowaniu. Położenie mieszkania musi być takie, aby odległość najdalszego chińczyka była jak najmniejsza, ponieważ Kozik lubi jeść, ale nie lubi dużo chodzić, a chciałby obejrzeć wszystkie chińczyki w mieście.
Kozik nie lubi też dużo myśleć, dlatego pomóż mu wybrać odpowiednie mieszkanie. Zakładamy, że odległość między dwoma sąsiednimi skrzyżowaniami wynosi jeden.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę skrzyżowań. Drugi wiersz zawiera liczb całkowitych (). Jeśli jest równe 1, to oznacza, że przy -tym skrzyżowaniu znajduje się chińczyk, w przeciwnym wypadku chińczyka nie ma.
Kolejnych wierszy opisuje połączenia między skrzyżowaniami. Każdy wiersz zawiera dwie liczby całkowite i (), oznaczające, że skrzyżowania i są połączone bezpośrednią drogą. W testach wartych około punktów zachodzi dodatkowy warunek .
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą odległości najdalszego chińczyka dla mieszkania, które powinien wybrać Kozik. Jeżeli w mieście nie ma chińczyka, wypisz -1.
Dla danych wejściowych:
7 0 1 0 0 1 0 1 1 3 2 3 3 4 4 5 4 6 6 7
poprawną odpowiedzią jest:
2
Autor zadania: Jacek Tomasiewicz.