A. Wooden Castle
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

IT is hiding in the abandoned house. To get there children need to open the door with a tricky lock. The lock is in fact a tree with $$$n$$$ vertices, each of them is either white or black. The lock opens after every vertex is eliminated. For that purpose 2 operations are available:

  1. Change the color of one vertex.

  2. Set up a chain reaction eliminating a group of connected vertices of the same color. More formally, one vertex of color $$$c$$$ can be chosen, then the group of vertices of color $$$c$$$, which can be reached from the chosen vertex through the vertices of color $$$c$$$, will be eliminated.

Naturally, the children want to get inside sooner, so they wonder how many operations are needed to open the lock.

Input

The first line contains $$$n$$$ — the number of vertices in the graph. ($$$1 \le n \le 200\,000$$$). The next line contains a string $$$s$$$ of the length $$$n$$$ consisting of $$$0$$$ and $$$1$$$. If the $$$i$$$-th symbol of the string $$$s$$$ is $$$0$$$, than $$$i$$$-th vertex is white, otherwise  — it is black. The next $$$n - 1$$$ lines contain 2 integer numbers each $$$a_i$$$ and $$$b_i$$$ — the edges of the tree ($$$1 \le a_i, b_i \le n$$$).

It is guaranteed that the edges form a tree.

Output

Output one number — the minimum number of operations needed to open the lock.

Example
Input
4
1000
1 2
1 3
1 4
Output
2
Note

In the first test case the lock can be open with 2 operations as follows:

  1. Change the color of vertex $$$1$$$ to white.
  2. Set up a chain reaction from vertex $$$1$$$, which will eliminate every vertex.