给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。
回想一下,简单路径是最多访问每个顶点一次的路径。令路径的权重为其所包含的顶点上写入的值的按位异或。假设如果没有简单路径的权重 $$$0$$$,那么一棵树就是好树。
您可以多次应用以下操作(可能为零):选择树的一个顶点,并将其上写入的值替换为任意正整数。为了使树变得良好,您必须应用此操作的最少次数是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 顶点数。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i < 2^{30}$$$) - 写在顶点上的数字。
接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n; x \ne y$$$) 表示连接顶点 $$$x$$$ 和顶点 $$$y$$$ 的边。保证这些边形成一棵树。
输出
打印单个整数 - 为了使树良好而必须应用该操作的最少次数。
示例
输入 #1
6 3 2 1 3 2 1 4 5 3 4 1 4 2 1 6 1
输出 #1
2
输入 #2
4 2 1 1 1 1 2 1 3 1 4
输出 #2
0
输入 #3
5 2 2 2 2 2 1 2 2 3 3 4 4 5
输出 #3
2
注意
在第一个示例中,将顶点 $$$1$$$ 上的值替换为 $$$13$$$ 并将顶点 $$$4$$$ 上的值替换为 $$$42$$$ 就足够了。