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 light bulbs connected by 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 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 order
they appear in the sequence. Since Fabijan reaaaly 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 contanins an integer , the number of light bulbs. Bulbs are labeled by integers from to .

The second line contans a sequence of characters `0`

and `1`

. If the -th character is equal to `0`

,
then in the beginning the -th bulb is turned off, and if it's equal to `1`

, it's turned on.

Each of the following lines contains two integers and – 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 .

Subtask | Score | Constraints |
---|---|---|

Each bulb is directly connected with at most two other bulbs. | ||

All bulbs are turned off in the beginning. | ||

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 .

#### 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`

## Comments