You are given a tree containing nodes where each node is coloured black or white. The -th edge is bidirectional and connects the nodes and . 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

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 , and .

##### Subtask 3 [80%]

No additional constraints.

#### Input Specification

The first line of input contains a single integer, .

The second line of input contains a string of characters, each character being either `B`

or `W`

. The -th node is black if the -th character is `B`

, and white otherwise.

The following lines of input contain two space-separated integers and , representing that there is a bidirectional edge between and 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

## Comments