In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.