Дано дерево из \(n\) вершин. На каждой вершине дерева записано число; на \(i\)-й вершине записано число \(a_i\).
Напомним, что простой путь — это путь, посещающий каждую вершину не более одного раза. Назовем весом пути побитовое исключающее ИЛИ значений записанных на его вершинах. Скажем, что дерево хорошее, если в нем не существует ни одного простого пути с весом \(0\).
Вы можете применить следующую операцию произвольное количество раз (возможно, ноль): выбрать вершину дерева и заменить значение записанное на ней на произвольное положительное целое число. Какое минимальное количество раз необходимо применить данную операцию, чтобы дерево стало хорошим?
Выходные данные
Выведите одно целое число — минимальное количество раз, которое необходимо применить операцию, чтобы дерево стало хорошим.
Примечание
В первом примере можно заменить значение на вершине \(1\) на \(13\), а значение на вершине \(4\) — на \(42\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 2 1 3 2 1
4 5
3 4
1 4
2 1
6 1
|
2
|
|
2
|
4
2 1 1 1
1 2
1 3
1 4
|
0
|
|
3
|
5
2 2 2 2 2
1 2
2 3
3 4
4 5
|
2
|