問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点からなる木があります。 $i$ 番目の辺は頂点 $x_i$ と $y_i$ を結んでいます。 各頂点は、白か黒のいずれかの色で塗られています。 初期状態では、頂点 $i$ の色は $c_i$ で表されます。 $c_i$ \= W のとき 頂点が白いことを、$c_i$ \= B のとき 頂点が黒いことを表します。

この木の頂点の上を猫が移動していきます。 具体的には、$1$ 秒間に次の動作のどちらかを行なうことを繰り返します。

• 現在いる頂点と隣接した頂点をひとつ選びその頂点に移動する。その後、移動先の頂点の色を反転する。
• 現在いる頂点の色を反転する。

猫の目標はすべての頂点を黒で塗ることです。どの頂点から動作をはじめても、どの頂点で動作を終えてもかまいません。 最短何秒で目標を達成できるでしょうか?

制約

• $1$ $≤$ $N$ $≤$ $10^5$
• $1$ $≤$ $x_i,y_i$ $≤$ $N$ ($1$ $≤$ $i$ $≤$ $N-1$)
• 与えられるグラフは木
• $c_i$ \= W または $c_i$ \= B

入力

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_{N-1}$ $y_{N-1}$ $c_1c_2..c_N$

出力

目標を達成するために必要な秒数の最小値を出力せよ。

入力例 1

5
1 2
2 3
2 4
4 5
WBBWW

出力例 1

5

例えば、次のように行動すると $5$ 秒で達成できます。

• 頂点 $1$ からはじめる。 頂点 $1$ の色を黒に変更する。
• 頂点 $2$ に移動し、頂点 $2$ の色を白に変更する。
• 頂点 $2$ の色を黒に変更する。
• 頂点 $4$ に移動し、頂点 $4$ の色を黒に変更する。
• 頂点 $5$ に移動し、頂点 $5$ の色を黒に変更する。

入力例 2

6
3 1
4 5
2 6
6 1
3 4
WWBWBB

出力例 2

7

入力例 3

1
B

出力例 3

0

入力例 4

20
2 19
5 13
6 4
15 6
12 19
13 19
3 11
8 3
3 20
16 13
7 14
3 17
7 8
10 20
11 9
8 18
8 2
10 1
6 13
WBWBWBBWWWBBWWBBBBBW

出力例 4

21