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