如果取消原题生成图结构的限制，并不是所有数据都是根号分治 + bitset 比三元环计数要快，且能稳定在 1s 内通过。因此提供该 Hack 数据提交，供性能测试。

时间限制： 5.0 秒

空间限制： 2048 MB

题目描述

本题中，我们考虑的图都是无向图，且没有自环，没有重边，边上无权值，每个点上标有一个字符，为 C、S 或 P。

我们称一个图是“CCSP图”，当且仅当该图满足以下所有条件：

• 有 4 个点、4 条边的连通图；
• 4 个点上的字符（不考虑顺序）为两个 C、一个 S、一个 P；
• 图中存在一个长度为 3 的环。

现在，给你一个图，你需要统计其中“CCSP子图”的个数。即你需要在图中选出 4 个点与 4 条连接这些点的边，统计多少种选法会使得选出的图是“CCSP图”。

注意：如果两种选法选取的点相同而边不同，也认为是不同的选法。

输入格式

从标准输入读入数据。

第一行包含两个整数 $n, m$，分别表示图的点数和边数。

第二行包含一个长度为 $n$ 的仅包含 C、S、P 的字符串，其中第 $i$ 个字符表示 $i$ 号点上的字符。

接下来 $m$ 行，每行包含两个整数。设其中第 $j$ 行的整数分别为 $u_j, v_j$，则表示存在一条连接 $u_j$ 与 $v_j$ 的边。

图上的点以从 $1$ 到 $n$ 的不同正整数编号；保证输入的图没有自环与重边；每行相邻的两个整数之间用一个空格隔开。

输出格式

输出到标准输出。

仅输出一行，包含一个整数，表示图中“CCSP子图”的个数。

4 5
SCPC
1 2
2 3
3 4
4 1
1 3

4

7 10
CCCSSPP
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
2 4
3 7

5

子任务

对于所有的数据，保证 $0 \leq n, m \leq 10^6$，每条边满足 $1 \leq u_j, v_j \leq n$。

前 4 组数据的具体生成方式如下：

• 人工指定 $n, m$；
• 独立生成每个点的字符，其中 C 的概率为 $1/2$，S 与 P 的概率各为 $1/4$；
• 依次生成每一条边：每个点被连接的概率正比于它的度数+$1/\sqrt{n}$，但是如果生成出了自环或重边，则丢弃之并重新生成。

最后一组数据的生成方式如下：

• 人工指定 $n, m$；
• 独立生成每个点的字符，其中 C 的概率为 $1/2$，S 与 P 的概率各为 $1/4$；
• 指定 10 个度数超大的点，按照一定的概率将边连到这些点上（两个端点设置的概率分别为 $0.7$ 和 $0.5$）。但是如果生成出了自环或重边，则丢弃之并重新生成。