Chinese Restaurants

Interview

Time limit1sMemory limit128 MB

Summary

Pick the intersection that minimizes the farthest distance to a marked restaurant and report that distance, or -1 when no restaurant exists.

Level: Medium5 of 10
Topics: Tree, BFS
Solved: No attempts yet

Problem

The capital has $n$ intersections and $n-1$ roads connecting them. The road network is built so that from any intersection you can reach any other intersection by exactly one route; in other words, the whole network forms a tree. Some intersections have a Chinese restaurant.

Kozik wants to live in the capital and plans to choose an apartment located at one of the intersections. He loves eating but hates walking a lot, so he wants his apartment placed where the distance to the farthest Chinese restaurant is as small as possible, while still being able to visit every Chinese restaurant in the city.

Help Kozik by finding the distance to the farthest Chinese restaurant from the intersection where his chosen apartment sits. Assume the distance between two adjacent intersections is $1$ .

Input

The first line contains the number of intersections $n$ ( $2 \le n \le 10^6$ ).

The second line contains $n$ integers $s_1, s_2, \dots, s_n$ ( $0 \le s_i \le 1$ ). If $s_i$ is $1$ , there is a Chinese restaurant at the $i$ -th intersection; if it is $0$ , there is none.

Each of the next $n-1$ lines contains two integers $a$ and $b$ ( $1 \le a, b \le n$ ), meaning intersections $a$ and $b$ are directly connected by a road.

Output

Print a single integer on one line: the distance to the farthest Chinese restaurant from the apartment Kozik should choose. If the city has no Chinese restaurant, print $-1$ .

Examples3

Example 1

Input

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

Expected output

Example 2
Input
```
2
1 0
1 2
```
Expected output
```
0
```
Example 3
Input
```
2
0 0
1 2
```
Expected output
```
-1
```