AT_arc097_d [ARC097F] Monochrome Cat

[problemUrl]: https://atcoder.jp/contests/arc097/tasks/arc097_d 頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点からなる木があります。 $ i $ 番目の辺は頂点 $ x_i $ と $ y_i $ を結んでいます。 各頂点は、白か黒のいずれかの色で塗られています。 初期状態では、頂点 $ i $ の色は $ c_i $ で表されます。 $ c_i $ $ = $ `W` のとき 頂点が白いことを、$ c_i $ $ = $ `B` のとき 頂点が黒いことを表します。 この木の頂点の上を猫が移動していきます。 具体的には、$ 1 $ 秒間に次の動作のどちらかを行なうことを繰り返します。 - 現在いる頂点と隣接した頂点をひとつ選びその頂点に移動する。その後、移動先の頂点の色を反転する。 - 現在いる頂点の色を反転する。 猫の目標はすべての頂点を黒で塗ることです。どの頂点から動作をはじめても、どの頂点で動作を終えてもかまいません。 最短何秒で目標を達成できるでしょうか?

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_{N-1} $ $ y_{N-1} $ $ c_1c_2..c_N $

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

### 制約 - $ 1 $ $