410263: GYM103994 E Самостоятельные деревья

E. Самостоятельные деревьяограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Дано дерево (связный граф с $$$n$$$ вершинами и $$$n-1$$$ ребрами), в каждой вершине которого находится неотрицательное целое число. Назовём дерево самостоятельным, если побитовое исключающее ИЛИ всех чисел в его вершинах равно $$$0$$$. Вам нужно найти, на какое максимальное количество самостоятельных деревьев можно разбить изначальное дерево, или сказать, что разбить изначальное дерево на самостоятельные деревья невозможно.

Разбиение дерева — это удаление из него нескольких рёбер. Можно показать, что в результате такой операции граф превратится в несколько непересекающихся деревьев.

Исключающее ИЛИ — это логическая операция, обозначаемая знаком $$$\oplus$$$, которая задаётся следующей таблицей истинности:

$$$x$$$	$$$y$$$	$$$x \oplus y$$$
0	0	0
0	1	1
1	0	1
1	1	0

Побитовое исключающее ИЛИ двух неотрицательных целых чисел $$$x$$$ и $$$y$$$ тоже обозначается $$$x \oplus y$$$ и определяется следующим образом: запишем числа $$$x$$$ и $$$y$$$ в двоичной системе счисления, дополнив при необходимости более короткое из них ведущими нулями до равной длины. Тогда $$$x \oplus y$$$ это целое неотрицательное число, каждый разряд которого в двоичной системе счисления является исключающим ИЛИ соответствующих разрядов чисел $$$x$$$ и $$$y$$$. Например, $$$5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$$$.

Побитовое исключающее ИЛИ нескольких чисел можно посчитать, применяя последовательно операцию $$$\oplus$$$ к предыдущему результату. Например, $$$a \oplus b \oplus c \oplus d$$$ = $$$((a \oplus b) \oplus c) \oplus d$$$. Можно показать, что результат не зависит от порядка вычисления.

Входные данные

В первой строке дано одно число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество вершин дерева.

В следующих $$$n-1$$$ строках вводятся по 2 числа $$$u$$$ и $$$v$$$ — концы рёбер дерева.

В последней строке находятся $$$n$$$ чисел $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — числа в вершинах дерева.

Выходные данные

В единственной строке выведите максимальное количество самостоятельных деревьев, на которое можно разбить данное дерево, или «-1», если такого разбиения не существует.

ПримерыВходные данные

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

Выходные данные

3

Входные данные

3
1 2
2 3
1 1 1

Выходные данные

-1

Примечание

В первом тесте дерево выглядит так:

Если удалить рёбра, обозначенные крестиком, то мы получим 3 самостоятельных дерева. Можно показать, что на большее количество разбить нельзя.