E. XOR дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$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$$$.