题目描述

ak 机有一颗有$n$个节点的树，其中每个节点是红色或者黑色，她想知道，删除一个红色节点以及与它相连的全部边后，剩余连通快中黑色节点数量的最大值是多少。

对于树上的两个点，如果它们相互连通，则称他们位于同一个连通快里；显然，在执行删除操作后，剩余部分至多构成两个连通块。

输入描述

第一行输入一个整数 $n$（$1\le n\le 10^5$）代表节点的数量。

第二行输入一个长度为$n$的字符串$s_1s_2...s_n(s_i\in ['R','B'])$代表第$i$个节点的颜色为$s_i$。若$s_i$为‘$B$’表示节点的颜色为黑色，若$s_i$为‘$R$’则表示节点的颜色为红色。保证$s$中至少有一个红色节点。

此后$n-1$行，第$i$行输入两个整数$u_i,v_i(1\le u_i,v_i\le n)$表示树上第$i$条边连接节点$u_i$和$v_i$。

输出描述

在一行上输出一个整数代表最大值

样例

输入

10
RRBBBBBBBB
1 2
1 3
1 4
1 5
1 7
2 8
4 6
4 10
6 9

输出

7