Autobiography

Bobo has an undirected graph with $n$ vertices and $m$ edges. The vertices are numbered by $1, \dots, n$, and the $i$-th edge is between the $a\_i$-th and the $b\_i$-th vertex. Plus, the $i$-th vertex is associated with a character $c\_i$.

Find the number of ways to choose four distinct vertices $(u, v, w, x)$ such that

• $u$ and $v$, $v$ and $w$, $w$ and $x$ are connected by an edge,
• $c\_u = \mathtt{b}$, $c\_v = \mathtt{o}$, $c\_w = \mathtt{b}$, $c\_x = \mathtt{o}$.

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains two integers $n$ and $m$.

The second line contains $n$ characters $c\_1 \dots c\_n$.

For the following $m$ lines, the $i$-th line contains two integers $a\_i$ and $b\_i$.

For each test case, output an integer which denotes the number of ways.

• $4 \le n \le 2 \times 10^5$
• $0 \le m \le 2 \times 10^5$
• $c\_i \in \\{\mathtt{b}, \mathtt{o}\\}$ for each $1 \leq i \leq n$
• $1 \leq a\_i, b\_i \leq n$ for each $1 \leq i \leq m$
• $a\_i \neq b\_i$ for each $1 \leq i \leq m$
• $\\{a\_i, b\_i\\} \neq \\{a\_j, b\_j\\}$ for each $1 \leq i < j \leq m$
• In each input, the sum of $n$ does not exceed $2 \times 10^5$. The sum of $m$ does not exceed $2 \times 10^5$.

For the first test case, there are $2$ quadrangles $(1, 3, 4, 5)$, $(2, 3, 4, 5)$.

For the second test case, there are $4$ quadrangles $(1, 2, 3, 4)$, $(1, 4, 3, 2)$, $(3, 2, 1, 4)$, $(3, 4, 1, 2)$.

For the third test case, there are no valid quadrangles.