Oh no! It's nighttime, and little Fabijan is afraid of the dark. To make things worse, the chandelier in his room is broken.

The chandelier is made up of $n$ light bulbs connected by $n-1$ wires, so that each wire connects two bulbs and all bulbs are connected, either directly or through other bulbs. In other words, the chandelier is a tree.

Each bulb has a button that changes its state. If the bulb is turned off, pressing the button turns it on, and if it's on, it turns it off. In the beginning, some bulbs are on and some are off (it's possible that all are turned off). All $n$ bulbs need to be turned on in order for Fabijan to stop being afraid, since only then will there be enough light in the room.

Fabijan will choose some sequence of bulbs such that bulbs that are consecutive in the sequence are directly connected by some wire. Bulbs can be repeated. He will then go around the bulbs in the order they appear in the sequence. Since Fabijan reaaally likes pressing buttons, either on light bulbs, washing machines, or in elevators, each time he visits a bulb he will press the corresponding button once, changing its state.

Help Fabijan and determine the length of the shortest sequence of bulbs such that in the end all bulbs are turned on. There will be at least one bulb that is turned off in the beginning.

Input

The first line contains an integer $n$, the number of light bulbs. Bulbs are labeled by integers from $1$ to $n$.

The second line contains a sequence of $n$ characters 0 and 1. If the $i$-th character is equal to 0, then in the beginning the $i$-th bulb is turned off, and if it's equal to 1, it's turned on.

Each of the following $n-1$ lines contains two integers $x$ and $y$ $(1\le x,y\le n)$ – labels of light bulbs that are directly connected by a wire.

Output

Output the minimum possible length of a sequence such that all bulbs are turned on in the end.

It can be proven that such a sequence always exists.

Scoring

In all subtasks, it holds that $2\le n\le 500000$.

Subtask	Score	Constraints
$1$	$20$	$2\le n\le 100$
$2$	$30$	Each bulb is directly connected with at most two other bulbs.
$3$	$30$	All bulbs are turned off in the beginning.
$4$	$30$	No additional constraints.

Sample Input 1

3
010
1 2
2 3

Sample Output 1

4

Explanation for Sample Output 1

Fabijan can choose the sequence $1,2,3,2$.

Sample Input 2

5
00000
1 2
2 3
2 4
3 5

Sample Output 2

7

Sample Input 3

5
00100
1 2
2 3
2 4
3 5

Sample Output 3

8