Dany jest drzewo nieskierowane o $N$ wierzchołkach, ponumerowanych od $1$ do $N$.

W drzewie znajdują się wierzchołki specjalne. Chcemy dodać do drzewa pewną liczbę krawędzi tak, aby utworzyć ścieżkę, która odwiedza każdy wierzchołek specjalny dokładnie raz. W trakcie przechodzenia ścieżki nie wolno odwiedzić żadnego wierzchołka dwukrotnie. Wierzchołki, które nie są specjalne, mogą znaleźć się na ścieżce, ale nie muszą być odwiedzone.

Oblicz minimalną liczbę krawędzi, które należy dodać, aby utworzyć ścieżkę odwiedzającą wszystkie wierzchołki specjalne dokładnie raz.

Wejście

W pierwszej linii podano liczbę wierzchołków $N$ $(1 \leq N \leq 200\,000)$.

W kolejnych $N-1$ liniach podano pary liczb $u, v$ oznaczające krawędzie łączące wierzchołki $(1 \leq u, v \leq N)$.

W $(N+1)$-szej linii podano $N$ liczb całkowitych oddzielonych spacjami. Jeśli $i$-ta liczba wynosi $0$, to wierzchołek $i$ jest wierzchołkiem zwykłym, a jeśli wynosi $1$, to wierzchołek $i$ jest wierzchołkiem specjalnym.

Graf podany na wejściu jest drzewem.

Wyjście

Wypisz minimalną liczbę krawędzi, które należy dodać, aby utworzyć ścieżkę.

Przykład

Wejście 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

Wyjście 1

4

Wejście 2

4
1 2
2 3
3 4
0 0 0 0

Wyjście 2

0

Wejście 3

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

Wyjście 3

1