题目描述

译自 COCI 2020/2021 Contest #2 T5「Svjetlo」

哦不！已经到晚上了。小 Fabijan 怕黑，更糟的是，他房间内的枝形吊灯坏了。

枝形吊灯由用 $n-1$ 条电线连接的 $n$ 个灯泡组成，每条电线连接两个灯泡，并且所有灯泡要么直接相连，要么通过其他灯泡相连。换句话说，枝形吊灯呈现树的结构。

每个灯泡都有一个能使其状态改变的开关。如果灯泡是灭的，按下开关就会使它变亮，如果它是亮的，按下开关就会使它变灭。刚开始的时候，一些灯泡是亮的，一些灯泡是灭的（可能刚开始所有灯泡都是灭的）。为了让小 Fabijan 不害怕，需要让所有 $n$ 个灯泡都是亮的，因为这样屋内才能足够亮。

Fabijan 会选择一个包含一些灯泡的序列，灯泡序列中两个相邻的灯泡被一些电线直接相连。序列中灯泡可以重复。他会按灯泡在灯泡序列中出现的顺序遍历这些灯泡。因为 Fabijan 超级喜欢按按钮，无论是灯泡上的，洗衣机上的还是电梯里的，每次他到达一个灯泡的位置的时候她就会按一次这个灯泡的开关，然后这个灯泡的状态就会改变。

请帮助 Fabijan 确定能使所有灯泡都变亮的最短的灯泡序列长度。最初至少有一个灯泡是灭的。

输入格式

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

第二行包含一个长度为 $n$ 且只包含 0 和 1 的字符串。如果第 $i$ 个字符是 0，则表示最初第 $i$ 个灯泡是灭的，如果是 1 则表示它是亮的。

接下来 $n-1$ 行，每行包含两个整数 $x,y$，表示直接被一条电线相连的两个灯泡的编号。

输出格式

输出能使所有灯泡都变亮的最短灯泡序列的长度。

可以证明这样的序列永远是存在的。

样例 1

3
010
1 2
2 3

4

Fabijan 可以选择序列 $1,2,3,2$。

5
00000
1 2
2 3
2 4
3 5

7

5
00100
1 2
2 3
2 4
3 5

8

数据范围与提示

对于所有子任务，保证 $2\le n\le 5\times 10^5,1\le x,y,\le n$。

详细子任务附加限制与分值如下表：