You are given a tree containing $N$ nodes where each node is coloured black or white. The $i$-th edge is bidirectional and connects the nodes $u_i$ and $v_i$. Find the number of simple paths containing at least three nodes of the same colour.

Note that traversing a path from either end counts as the same path.

Constraints

$3\le N\le 2\times {10}^5$

$1\le u_i,v_i\le N,u_i\ne v_i$

It is guaranteed that the graph described in the input is a tree.

Subtask 1 [10%]

All nodes are black.

Subtask 2 [10%]

The graph is linear. More specifically, for $1\le i<N$, $u_i=i$ and $v_i=i+1$.

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line of input contains a single integer, $N$.

The second line of input contains a string of $N$ characters, each character being either B or W. The $i$-th node is black if the $i$-th character is B, and white otherwise.

The following $N-1$ lines of input contain two space-separated integers $u_i$ and $v_i$, representing that there is a bidirectional edge between $u_i$ and $v_i$ in the tree.

Output Specification

Output a single integer, representing the number of simple paths containing at least three nodes of the same colour.

Sample Input

5
BBBWB
1 2
4 2
5 2
1 3

Sample Output

4

Explanation

The simple paths in the graph with at least three nodes of the same colour are the paths between nodes:

• 1 and 5
• 2 and 3
• 3 and 4
• 3 and 5