Дан неориентированный граф, являющийся деревом с $N$ вершинами, пронумерованными от $1$ до $N$.

В дереве есть особые вершины. Мы хотим добавить в дерево дополнительные ребра так, чтобы создать путь, проходящий через каждую особую вершину ровно один раз. При этом нельзя посещать одну и ту же вершину дважды. Обычные (не особые) вершины могут быть включены в путь, но посещать все обычные вершины не требуется.

Найдите минимальное количество ребер, которые необходимо добавить, чтобы создать путь, проходящий через все особые вершины ровно один раз.

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

В первой строке дано количество вершин $N$ $(1 \leq N \leq 200\,000)$.

В следующих $N-1$ строках даны пары чисел $u, v$, описывающие ребра дерева $(1 \leq u, v \leq N)$.

В $(N+1)$-й строке даны $N$ целых чисел, разделенных пробелами. Если $i$-е число равно $0$, то вершина $i$ является обычной, если $1$ — то особой.

Гарантируется, что заданный граф является деревом.

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

Выведите минимальное количество ребер, которые необходимо добавить для создания пути.

Примеры

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

21
1 2
1 3
2 4
2 5
3 6
3 7
3 8
3 9
4 10
5 11
5 12
6 13
6 14
10 15
10 16
13 17
16 18
16 19
17 20
17 21
0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0

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

4

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

4
1 2
2 3
3 4
0 0 0 0

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

0

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

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

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

1