← 返回题目列表

Codeforces · 229/C

C. 三角形

中文机器翻译题面 查看原题

Alice 和 Bob 不再玩游戏了。现在他们一起研究各种图的属性。 Alice 发明了以下任务:她采用一个具有 n 个顶点的完整无向图,选择一些 m 个边并保留它们。 Bob 获得 $${ \frac { n ( n - 1 ) } { 2 } } - m$$ 剩余边。

Alice和Bob喜欢图中的“三角形”,即长度为3的循环。这就是为什么他们想知道:Alice和Bob的边形成的两个图中相应的三角形总数是多少?

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106) — 相应地,初始完整图中的顶点数和 Alice 图中的边数。然后是 m 行:第 i 行包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), — Alice 图中第 i 条边连接的两个顶点的数量。保证Alice的图不包含重边和自环。保证初始完全图也不包含重边和自环。

考虑图顶点以某种方式从 1 到 n 进行索引。

输出

打印一个数字——Alice 和 Bob 图中长度为 3 的循环总数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。建议使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

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

输出 #1

3

输入 #2

5 3
1 2
2 3
1 3

输出 #2

4

注意

在第一个样本中,Alice 有 2 个三角形:(1, 2, 3) 和 (2, 3, 4)。 Bob 的图只有 1 个三角形:(1, 4, 5)。这就是为什么这两个图总共包含 3 个三角形。

在第二个示例中,Alice 的图只有一个三角形:(1, 2, 3)。 Bob 的图有三个三角形:(1,4,5)、(2,4,5) 和 (3,4,5)。在这种情况下,问题的答案是 4。