JOI 発電所には、$1$ から $N$ までの番号が付いた $N$ 個の拠点がある。拠点は $N-1$ 本の電線で結ばれている。$i$ 番目の電線 ($1 \le i \le N-1$) は拠点 $A_i$ と拠点 $B_i$ を双方向に結ぶ。いくつかの電線を通って、任意の拠点から他の任意の拠点へ移動できる。

JOI 発電所の各拠点には、発電機が高々 1 台ある。各発電機にはスイッチがあり、最初はすべての発電機のスイッチがオフになっている。あなたは JOI 発電所の所長である。いくつかの発電機を選び、選んだ発電機のスイッチをオンにすることができる。（何も選ばなくてもよい。）発電機には次の性質がある。

• 拠点 $x,y,z$ に発電機があるとする。また、同じ電線を 2 回通ることなく、拠点 $x$ から拠点 $y$、拠点 $y$ から拠点 $z$ の順に移動できるとする。拠点 $x$ と拠点 $z$ の発電機のスイッチがオンならば、拠点 $y$ の発電機は故障する。
• 発電機は、スイッチがオンであり、かつ故障していないときに稼働する。

最後に、稼働した発電機から報酬を得る。稼働した発電機 1 台につき 1 円を受け取る。ただし、故障した発電機の修理費も支払わなければならない。故障した発電機 1 台につき 1 円を支払う。報酬の合計から修理費の合計を引いた額が、あなたの利益となる。

拠点と電線の配置、および発電機の情報が与えられたとき、利益の最大値を求めるプログラムを作成せよ。

入力

標準入力から以下のデータを読み込め。

$$ \begin{gathered} N\\ A_1\quad B_1\\ \vdots\\ A_{N-1}\quad B_{N-1}\\ S \end{gathered} $$

ここで $S$ は、各拠点の発電機を表す長さ $N$ の文字列である。$S$ の各文字は 0 または 1 である。$i$ 文字目 ($1 \le i \le N$) は拠点 $i$ の発電機を表し、拠点 $i$ に発電機がなければ 0、あれば 1 である。

出力

標準出力に 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$ は 0 と 1 からなる長さ $N$ の文字列である。
• $S$ は少なくとも 1 つの 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$ のスイッチをオンにすると、拠点 $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