CF229C Triangles

Alice 和 Bob 不再玩游戏了。现在他们一起研究各种图的性质。Alice 想出了如下任务：她取一个包含 $n$ 个顶点的完全无向图，选择其中的 $m$ 条边并保留下来。剩下的边都归 Bob 所有。 Alice 和 Bob 都很喜欢图中的“三角形”，也就是长度为 $3$ 的环。因此，他们想知道：由 Alice 和 Bob 各自拥有的边所构成的两幅图中，一共包含多少个三角形（长度为 $3$ 的环）？

第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \leq n \leq 10^{6}$，$0 \leq m \leq 10^{6}$），分别表示初始完全图的顶点数和 Alice 图中的边数。接下来 $m$ 行，每行包含两个用空格分隔的整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示 Alice 图的第 $i$ 条边连接 $a_i$ 与 $b_i$ 两个顶点。保证 Alice 的图中没有重边和自环；初始的完全图同样没有重边和自环。 假设图中的顶点编号为 $1$ 到 $n$。

输出一个整数，表示 Alice 和 Bob 的图（分别由他们各自掌握的边构成）中一共包含多少个长度为 $3$ 的环。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。建议使用 cin、cout 流或 %I64d 进行读写。

在第一个样例中，Alice 的图有 $2$ 个三角形：(1, 2, 3) 和 (2, 3, 4)。Bob 的图只有 $1$ 个三角形：(1, 4, 5)。因此，两幅图中共包含 $3$ 个三角形。 在第二个样例中，Alice 的图只包含 $1$ 个三角形：(1, 2, 3)。Bob 的图包含 $3$ 个三角形：(1, 4, 5)、(2, 4, 5) 和 (3, 4, 5)。因此本题答案为 $4$。 由 ChatGPT 5 翻译