F. Far Far Away
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the magical land of Duloc lies Shrek's beautiful swamp. Shrek is currently in Duloc, but he wants to reach the kingdom of Far Far Away as soon as possible so he can meet Princess Fiona.

There are $$$n$$$ locations in the Shrek universe that are connected by $$$n - 1$$$ bidirectional roads, each of which joins two distinct locations. Location $$$1$$$ is Duloc, and location $$$n$$$ is the kingdom of Far Far Away. It takes Shrek exactly one hour to travel across a single road, and it is guaranteed that Shrek can reach any location from any other location by traveling along a sequence of roads.

His journey isn't this simple however. Some (possible none or all) of the locations in the Shrek universe contain uncooked vegetables. Since Shrek loves uncooked vegetables, he must travel to and eat every uncooked vegetable in the Shrek universe before finishing his journey. Please help Shrek find the minimum number of hours it will take for him to travel from Duloc to the kingdom of Far Far Away while eating every uncooked vegetable in the Shrek universe! Note that this may require him to visit the kingdom of Far Far Away multiple times.

Input

The first line of input will contain the integer $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — denoting the number of locations in the Shrek universe.

The second line of input will contain a bitstring $$$s$$$ of length $$$n$$$, where $$$s_i \in \{0, 1\}$$$ is equal to $$$1$$$ if and only if the $$$i$$$-th location contains an uncooked vegetable.

Each of the next $$$n - 1$$$ lines of input will contain two space-separated integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) — denoting a road between locations $$$a_i$$$ and $$$b_i$$$.

Output

Output a single integer, indicating the minimum number of hours that it will take for Shrek to complete his journey while eating every uncooked vegetable in the Shrek universe.

Examples
Input
5
01100
1 2
2 4
2 5
3 2
Output
4
Input
7
0000111
1 2
4 2
4 5
7 4
7 6
3 2
Output
7
Note

In the first testcase, there are uncooked vegetables in locations 2 and 3. Shrek can reach all of them by following the path 1 -> 2 -> 3 -> 2 -> 5, which will take him 4 hours. It can be proven that there is no way for Shrek to accomplish this in less time.

In the second testcase, Shrek can follow the path 1 -> 2 -> 4 -> 5 -> 4 -> 7 -> 6 -> 7.