31110번 - 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.