Problem Statement

In the garden of C's house, there is a tree that bears chihuahuas.
The tree is represented by a connected undirected graph with $N$ vertices and $N - 1$ edges. The vertices are numbered $1, 2, ..., N$.
Each vertex has the character 'c' or 'w' written on it, and one chihuahua can be harvested for each triple $(i, j, k)$ satisfying the following conditions.

• $i, j, k$ are mutually distinct integers between $1$ and $N$, inclusive.
• Vertices $i, j, k$ form a path in this order (that is, when following the shortest path from vertex $i$ to $j$ and then from $j$ to $k$, no edge is traversed two or more times).
• Vertex $i$ has the character 'c' written on it, and vertices $j, k$ have the character 'w' written on them.

Input

$N$
$S$
$a_1$ $b_1$
$a_2$ $b_2$
.
.
.
$a_{N-1}$ $b_{N-1}$

• The first line contains an integer $N$ $(3 \leq N \leq 100000)$, the number of vertices of the tree.
• The second line contains a string $S$ of length $N$.
• The $i$-th character $s_i$ of $S$ indicates that the character written on vertex $i$ is $s_i$.
• $S$ contains no characters other than 'c' and 'w'.
• From the 3rd line to the $N + 1$-th line, the edge information $a_i, b_i$ ($1 \leq i \leq N - 1,$ $a_i, b_i$ are integers between $1$ and $N$, inclusive) is given as space-separated integers.
• $a_i, b_i$ indicate that there is an edge connecting vertex $a_i$ and vertex $b_i$.
• No edge connects a vertex to itself. That is, $a_i \neq b_i$ for all $i$.
• The same edge is not given more than once. That is, for all $i, j$ $(1 \leq i < j \leq N - 1)$, "$a_i \neq a_j$ or $b_i \neq b_j$" and "$a_i \neq b_j$ or $b_i \neq a_j$" hold.
• Every vertex can be reached from every other vertex by passing through some edges.

Output

Output on one line the number of chihuahuas that can be harvested from the tree.
Note that the answer may not fit in a 32-bit integer type.
Print a newline at the end.

Sample

4
cwww
1 2
2 3
2 4

2

5
cwwwc
1 2
2 3
3 4
4 5

6

3
wcw
1 2
3 2

0