시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

W stolicy jest n skrzyżowań oraz n - 1 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ą n (2 ≤ n ≤ 106), oznaczającą liczbę skrzyżowań. Drugi wiersz zawiera n liczb całkowitych s1, s2, ..., sn (0 ≤ si ≤ 1). Jeśli si jest równe 1, to oznacza, że przy i-tym skrzyżowaniu znajduje się chińczyk, w przeciwnym wypadku chińczyka nie ma.

Kolejnych n - 1 wierszy opisuje połączenia między skrzyżowaniami. Każdy wiersz zawiera dwie liczby całkowite a i b (1 ≤ a, bn), oznaczające, że skrzyżowania a i b są połączone bezpośrednią drogą.

출력

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.

예제 입력 1

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

예제 출력 1

2