$1$ から $N$ までの $N$ 個の頂点からなる無向木がある。

この木には特別な頂点が存在する。木に辺を追加して、すべての特別な頂点を一度ずつ訪れる経路を作りたい。このとき、同じ頂点を二度訪れてはならない。特別な頂点ではない一般の頂点は経路に含まれてもよいが、すべての一般の頂点を訪れる必要はない。

すべての特別な頂点を一度ずつ訪れる経路を作るために必要な辺の最小数を求めよ。

入力

1行目に頂点の数 $N$ が与えられる。 $(1 \leq N \leq 200\,000)$

2行目から $N-1$ 行にわたって、辺が結ぶ2つの頂点の番号 $u, v$ が与えられる。 $(1 \leq u, v \leq N)$

$N+1$ 行目には $N$ 個の整数が空白区切りで与えられる。$i$ 番目の整数が $0$ であれば $i$ 番の頂点は一般の頂点であり、$1$ であれば $i$ 番の頂点は特別な頂点である。

入力として与えられるグラフは木である。

出力

経路を作るために追加すべき辺の最小数を出力せよ。

入出力例

入力 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