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。