有一棵拥有 $N$ 个节点的树。节点编号为 $1$ 到 $N$。

每个节点都被染成白色或黑色。你可以任意次交换两个相邻节点的颜色。最终树是指在原树上进行有限次交换后得到的树（即最终的颜色配置）。最终树的交换代价等于你进行的交换次数。

白树是最终树的一个连通子图，它用最少的边数连接了最终树中的所有白色节点。类似地，黑树是最终树的一个连通子图，它用最少的边数连接了最终树中的所有黑色节点。

最终树的边代价等于白树的边数与黑树的边数之和。请注意，边代价仅在所有交换完成后计算。

最终树的总代价是其交换代价与边代价之和。

求最终树的最小可能总代价。

输入格式

输入的第一行包含节点数 $N$。

输入的第二行包含一个长度为 $N$ 且仅由 W 和 B 组成的字符串 $s$。如果 $s$ 的第 $i$ 个字符是 W，则节点 $i$ 为白色；如果第 $i$ 个字符是 B，则节点 $i$ 为黑色。保证字符串 $s$ 中至少包含一个 W 和至少一个 B。

接下来的 $N - 1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

保证输入构成一棵合法的树。

输出格式

输出的第一行应包含最终树的最小可能总代价。

数据范围

• $2 \le N \le 5 \times 10^5$
• $1 \le u < v \le N$

样例

输入样例 1

4
WWBB
1 2
2 3
2 4

输出样例 1

3

输入样例 2

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

输出样例 2

7