暂无测试数据。

小 O 要给一棵圣诞树染色，但是因为他的失误，点没有被染成完全一样的颜色，有一部分被染成了白色，有一部分则是黑色。

小 O 尝试改变一些点的颜色，他每次可以选择一个渲染点 $x$ ，对于所有的点 $y$，如果满足 $x-y$ 路径上所有点颜色一样，则可以将 $y$ 的颜色反转，$y$ 可以等于 $x$。

现在小 O 想知道，他最少选择几次渲染点，就能让树上所有点颜色变成一样的？

注：树是一种由 $n$ 个点和 $n-1$ 条边组成的无向联通图。

输入格式

第一行，一个数 $n$ ，代表树上点的个数。

第二行，$n$ 个数，$0$ 或者 $1$，代表第 $i$ 个点的颜色，题目中的反转意为：$0$ 反转变为 $1$，$1$ 反转变为 $0$。

接下来 $n-1$ 行，每行两个数 $x,y$，代表 $x-y$ 是树上的一条边。

输出格式

一行，一个数，最少的选择渲染点次数，对同一个点可以选择多次。

数据规模与约定

对于 $30\%$ 的数据，$1 \leq n \leq 1000$；

对于 $100\%$ 的数据，$1\leq n \leq 10^6$

13
1 0 1 0 1 0 1 1 0 1 1 0 1
1 2
2 3
3 4
4 5
5 6
6 7
8 9
9 10
10 4
4 11
11 12
12 13

3