该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

33DAI 得到了一棵有 $n$ 个点的树，第 $i$ 个点上写着一个正整数 $a_i$。

一条简单路径是指经过每个点至多一次的路径。一条简单路径的权是这条路径上所有点上的数 的按位异或和。$\oplus$ 表示按位异或：把两个整数写成二进制后逐位比较，相同得 $0$、 不同得 $1$；在 C++ 中，按位异或写作 ^（例如 a ^ b）。例如一条经过点 $u, v, w$ 的路径，它的权就是 $a_u \oplus a_v \oplus a_w$。

如果一棵树中不存在权为 $0$ 的简单路径，就称它是好的。

33DAI 可以执行任意多次（也可以一次也不执行）如下操作：选择一个点，把写在这个点上的数替换成 任意一个正整数。33DAI 想知道，最少需要执行多少次操作，才能让这棵树变成好的。

输入格式

从文件 tree.in 读入数据。

第一行包含一个整数 $n$，表示树的点数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻两个整数之间用一个空格分隔。

接下来 $n-1$ 行，每行包含两个整数 $x$ 与 $y$，表示树上的一条边。

输出格式

输出到文件 tree.out。

输出一行一个整数，表示 33DAI 最少需要执行的操作次数。

6
3 2 1 3 2 1
4 5
3 4
1 4
2 1
6 1

2

样例 1 解释

把第 $1$ 个点上的数改成 $13$、第 $4$ 个点上的数改成 $42$，一共执行 $2$ 次操作； 此时树中任意一条简单路径的权都不等于 $0$，所以这组输出对应的方案是合法的。

4
2 1 1 1
1 2
1 3
1 4

0

样例 2 解释

一次操作也不执行时，树中任意一条简单路径的权都不等于 $0$，所以答案是 $0$。

5
2 2 2 2 2
1 2
2 3
3 4
4 5

2

样例 3 解释

把第 $2$ 个点上的数改成 $5$、第 $4$ 个点上的数改成 $6$，一共执行 $2$ 次操作； 此时树中任意一条简单路径的权都不等于 $0$，所以这组输出对应的方案是合法的。

样例 4

见 tree4.in 与 tree4.ans。

样例 5

见 tree5.in 与 tree5.ans。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 2 \times 10^5$；
• $1 \le a_i < 2^{30}$；
• $1 \le x, y \le n$ 且 $x \ne y$，并且给出的 $n-1$ 条边恰好构成一棵树。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。