糟糕！现在是深夜，小 Fabijan 很怕黑。更糟糕的是，他房间里的吊灯坏了。

吊灯由 $n$ 个灯泡和 $n - 1$ 根电线组成，每根电线连接两个灯泡，所有灯泡都直接或间接地相互连接。换句话说，吊灯的结构是一棵树。

每个灯泡都有一个可以改变其状态的按钮。如果灯泡是关闭的，按下按钮会将其打开；如果是打开的，按下按钮会将其关闭。在最开始，有些灯泡是打开的，有些是关闭的（可能所有灯泡都是关闭的）。只有当所有 $n$ 个灯泡都被打开时，房间里才会有足够的光亮，Fabijan 才会不再害怕。

Fabijan 将选择一个灯泡序列，使得序列中相邻的灯泡都由电线直接相连。序列中的灯泡可以重复。然后，他将按照灯泡在序列中出现的顺序依次访问它们。因为 Fabijan 非常喜欢按按钮（无论是灯泡、洗衣机还是电梯上的按钮），所以他每次访问一个灯泡时，都会按下该灯泡对应的按钮一次，从而改变其状态。

请帮助 Fabijan，求出使得最终所有灯泡都被打开的最短灯泡序列的长度。初始时，至少有一个灯泡是关闭的。

输入格式

第一行包含一个整数 $n$，表示灯泡的数量。灯泡用 $1$ 到 $n$ 的整数编号。

第二行包含一个由 $n$ 个字符 0 和 1 组成的序列。如果第 $i$ 个字符为 0，则表示初始时第 $i$ 个灯泡是关闭的；如果为 1，则表示它是打开的。

接下来的 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示由一根电线直接相连的两个灯泡的编号。

输出格式

输出一个整数，表示使得最终所有灯泡都被打开的序列的最小可能长度。

可以证明，这样的序列总是存在的。

子任务

对于所有子任务，均满足 $2 \le n \le 500\,000$。

样例

输入样例 1

3
010
1 2
2 3

输出样例 1

4

输入样例 2

5
00000
1 2
2 3
2 4
3 5

输出样例 2

7

输入样例 3

5
00100
1 2
2 3
2 4
3 5

输出样例 3

8

说明

对于第一个样例，Fabijan 可以选择序列 $1, 2, 3, 2$。