JOI 發電廠有 $N$ 個基地，編號由 $1$ 到 $N$。基地之間由 $N-1$ 條電線連接。第 $i$ 條電線（$1 \le i \le N-1$）雙向連接基地 $A_i$ 同基地 $B_i$。沿住若干條電線，可以由任何基地去到其他任何基地。

JOI 發電廠嘅每個基地最多有一部發電機。每部發電機都有一個開關。一開始，所有發電機嘅開關都係關閉嘅。你係 JOI 發電廠嘅廠長，可以揀一啲發電機，將佢哋嘅開關打開。（亦可以一部都唔揀。）發電機有以下特性。

• 假設基地 $x,y,z$ 都有發電機，而且可以依次由基地 $x$ 去基地 $y$、再由基地 $y$ 去基地 $z$，途中冇任何電線被經過兩次。如果基地 $x$ 同基地 $z$ 嘅發電機開關都係開啟嘅，基地 $y$ 嘅發電機就會損壞。
• 一部發電機如果開關係開啟嘅，而且冇損壞，就會運作。

最後，你會由運作緊嘅發電機獲得報酬，每部運作緊嘅發電機會畀你 1 日圓。不過，你亦要為損壞嘅發電機支付維修費，每部損壞嘅發電機要付 1 日圓。總報酬減去總維修費，就係你嘅利潤。

請寫一個程式，畀定基地同電線嘅配置，以及發電機嘅資料，計算你可以得到嘅最大利潤。

輸入格式

由標準輸入讀取以下資料。

$$ \begin{array}{ll} N &\\ A_1 & B_1\\ \vdots &\\ A_{N-1} & B_{N-1}\\ S & \end{array} $$

呢度嘅 $S$ 係一個長度為 $N$ 嘅字串，表示各個基地嘅發電機。$S$ 嘅每個字元都係 0 或者 1。第 $i$ 個字元（$1 \le i \le N$）描述基地 $i$ 嘅發電機。如果基地 $i$ 冇發電機，就係 0；如果有發電機，就係 1。

輸出格式

向標準輸出寫一行，包含你揀一啲發電機並將佢哋全部開關打開時，可以得到嘅最大利潤。

數據範圍

• $1 \le N \le 200\,000$。
• $1 \le A_i \le N$（$1 \le i \le N-1$）。
• $1 \le B_i \le N$（$1 \le i \le N-1$）。
• $A_i \ne B_i$（$1 \le i \le N-1$）。
• 沿住若干條電線，可以由任何基地去到其他任何基地。
• $S$ 係一個長度為 $N$，由 0 同 1 組成嘅字串。
• $S$ 最少包含一個 1。

子任務

1. （6 分）$N \le 16$。
2. （41 分）$N \le 2\,000$。
3. （53 分）冇額外限制。

樣例

輸入格式 1

6
2 3
4 3
1 3
3 5
6 2
110011

輸出格式 1

3

說明

喺呢個樣例，基地 $1,2,5,6$ 有發電機。

如果將基地 $1,2,5$ 嘅開關打開，呢三個基地嘅發電機都會運作，你會得到 $3$ 日圓。由於唔使支付維修費，所以利潤係 $3$ 日圓。呢個係最大利潤，因此輸出 $3$。

另一方面，如果將基地 $1,5,6$ 嘅開關打開，基地 $2$ 嘅發電機會損壞，而基地 $1,5,6$ 嘅發電機會運作。你會得到 $3$ 日圓，並支付 $1$ 日圓維修費，所以利潤係 $2$ 日圓。

如果將基地 $1,2,5,6$ 嘅開關打開，基地 $2$ 嘅發電機會損壞，而基地 $1,5,6$ 嘅發電機會運作。你會得到 $3$ 日圓，並支付 $1$ 日圓維修費，所以利潤係 $2$ 日圓。

輸入格式 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

輸出格式 2

3

輸入格式 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

輸出格式 3

5