Description

有一棵 $n$ 个节点的树，树上每个点 $i$ 有一个权值 $a_i$

你可以使用一次魔法将一个 $a_i$ 改变为任何你喜欢的值

求最少要使用多少次魔法才能使得：不存在两个点 $u,v$ ，满足 $u,v$ 简单路径上的点权值异或和为 $0$

Input

第一行一个正整数 $n$

第二行 $n$ 个正整数，表示数组 $a$

接下来 $n - 1$ 行每行两个数 $u,v$ ，表示树上的一条边

$1 \leq n \leq 3 \times 10^5 , 1 \leq a_i \leq 10^9$

Output

一行一个数，表示使用魔法的最少次数

Sample

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