給定一個由 $1$ 到 $N$ 共 $N$ 個頂點組成的無向樹。

樹中有一些特殊頂點。我們想要透過在樹中添加邊，使得存在一條路徑能夠恰好訪問每個特殊頂點一次。在此過程中，不能訪問同一個頂點兩次。非特殊頂點（一般頂點）可以包含在路徑中，但不需要訪問所有一般頂點。

請計算為了形成一條能恰好訪問每個特殊頂點一次的路徑，所需添加的最少邊數。

輸入格式

第一行輸入一個整數 $N$。$(1 \leq N \leq 200\,000)$

接下來 $N-1$ 行，每行輸入兩個整數 $u, v$，表示一條連接頂點 $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