题目描述

给定一棵由 $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$ 的边。保证这些边构成一棵树。

输出格式

输出一个整数——为了使这棵树变好，你最少需要执行多少次操作。

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

2

4
2 1 1 1
1 2
1 3
1 4

0

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

2

提示

在第一个样例中，只需将顶点 $1$ 上的值替换为 $13$ ，并将顶点 $4$ 上的值替换为 $42$ 即可。