Il existe un arbre non orienté composé de $N$ sommets, numérotés de $1$ à $N$.

Dans cet arbre, certains sommets sont des sommets spéciaux. Nous souhaitons ajouter des arêtes à l'arbre afin de créer un chemin qui visite chaque sommet spécial exactement une fois. Il est interdit de visiter le même sommet deux fois. Les sommets qui ne sont pas spéciaux peuvent être inclus dans le chemin, mais il n'est pas nécessaire de visiter tous les sommets non spéciaux.

Déterminez le nombre minimal d'arêtes à ajouter pour créer un chemin qui visite tous les sommets spéciaux exactement une fois.

Entrée

La première ligne contient le nombre de sommets $N$. $(1 \leq N \leq 200\,000)$

Les $N-1$ lignes suivantes contiennent chacune deux entiers $u$ et $v$ représentant une arête reliant les sommets $u$ et $v$. $(1 \leq u, v \leq N)$

La $(N+1)$-ième ligne contient $N$ entiers séparés par des espaces. Si le $i$-ième entier est $0$, alors le sommet $i$ est un sommet ordinaire ; s'il est $1$, alors le sommet $i$ est un sommet spécial.

Le graphe donné en entrée est un arbre.

Sortie

Affichez le nombre minimal d'arêtes à ajouter pour créer le chemin.

Exemples

Entrée 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

Sortie 1

4

Entrée 2

4
1 2
2 3
3 4
0 0 0 0

Sortie 2

0

Entrée 3

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

Sortie 3

1