T680285 [CCSP2019 Pre] CCSP 子图计数

**时间限制：** 1.0 秒 **空间限制：** 512 MB 注意：洛谷等 OJ 的空间占用计算方式为实际占用制（即只计算实际被写入内容的空间），而非 OI 当中使用的分配制（即开多大的数组都计算进去），因此在本题中你可以预先开启比 512MB 更大的数组空间。 由于 std 无法满足对应的时空限制，因此我们提供时限 2s 空间 2G 的[评测链接](https://www.smqyoj.com/p/CCSP2019A)。

本题中，我们考虑的图都是无向图，且没有自环，没有重边，边上无权值，每个点上标有一个字符，为 `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子图”的个数。

### 子任务 对于所有的数据，保证 $0 \leq n, m \leq 10^6$，每条边满足 $1 \leq u_j, v_j \leq n$。 本题以子任务的方式评测。每个子任务包含若干测试点，你需要通过某个子任务的所有测试点才能得到该子任务的分数。 | 子任务编号 | 分数 | $n,m\le$ | | :----: | :---: | :---: | | 1 | 14 | $3$ | | 2 | 34 | $4$ | | 3 | 21 | $10$ | | 4 | 13 | $100$ | | 5 | 8 | $1000$ | | 6 | 5 | $10^4$ | | 7 | 3 | $10^5$ | | 8 | 2 | $10^6$ | 除样例外的所有测试数据均为随机生成的，具体生成方式如下： * 人工指定 $n, m$； * 独立生成每个点的字符，其中 `C` 的概率为 $1/2$，`S` 与 `P` 的概率各为 $1/4$； * 依次生成每一条边：每个点被连接的概率正比于它的度数+$1/\sqrt{n}$，但是如果生成出了自环或重边，则丢弃之并重新生成。 ### 提示 本题最后的一些部分分难度较大而分数较少，性价比很低，请合理规划比赛时间。