Existe un árbol no dirigido compuesto por $N$ vértices numerados del $1$ al $N$.

El árbol tiene vértices especiales. Se desea añadir aristas al árbol para crear un camino que visite cada vértice especial exactamente una vez. En este proceso, no se debe visitar el mismo vértice dos veces. Los vértices que no son especiales pueden incluirse en el camino, pero no es necesario visitar todos los vértices no especiales.

Calcule el número mínimo de aristas necesarias para crear un camino que visite todos los vértices especiales exactamente una vez.

Entrada

La primera línea contiene el número de vértices $N$. $(1 \leq N \leq 200\,000)$

Desde la segunda línea, se proporcionan $N-1$ líneas, cada una con dos números $u, v$ que representan una arista que conecta los vértices $u$ y $v$. $(1 \leq u, v \leq N)$

En la línea $N+1$, se proporcionan $N$ números enteros separados por espacios. Si el $i$-ésimo entero es $0$, el vértice $i$ es un vértice normal; si es $1$, el vértice $i$ es un vértice especial.

El grafo proporcionado como entrada es un árbol.

Salida

Imprima el número mínimo de aristas que deben añadirse para crear el camino.

Ejemplos

Entrada 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

Salida 1

4

Entrada 2

4
1 2
2 3
3 4
0 0 0 0

Salida 2

0

Entrada 3

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

Salida 3

1