← 返回题目列表

AtCoder · arc205_b

B. 三角形切换

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

分数: 500 点

问题陈述

有一个完整的图表 N 顶点编号 1 to N。每个边缘都是黑色或白色。对于 i=1,2,\ldots,M,连接顶点的边 U_i 和 V_i 为黑色,所有其他边缘为白色。

您可以执行以下操作零次或多次。

  • 选择三个整数 (a,b,c) 满意 1\le a < b < c \le N,并重新绘制以下三个边缘:白到黑,黑到白。
    • 连接顶点的边 a 和 b
    • 连接顶点的边 b 和 c
    • 连接顶点的边 a 和 c

找到当您执行适当的操作时可以涂成黑色的最大边数。

约束

  • 3\le N\le 2\times 10^5
  • \displaystyle 0\le M\le 2\times 10^5
  • 1\le U_i < V_i \le N
  • (U_i , V_i) \neq (U_j , V_j) (i \neq j)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

输出

输出答案。


示例输入 1

4 1
1 2

示例输出 1

5

通过执行如下两个操作,可以使黑边的数量 5.

  • 选择 (a,b,c)=(1,3,4)。然后,我们有以下四个黑边。
    • 连接顶点的边 1 和 2
    • 连接顶点的边 1 和 3
    • 连接顶点的边 1 和 4
    • 连接顶点的边 3 和 4
  • 选择 (a,b,c)=(2,3,4)。然后,我们有以下五个黑边。
    • 连接顶点的边 1 和 2
    • 连接顶点的边 1 和 3
    • 连接顶点的边 1 和 4
    • 连接顶点的边 2 和 3
    • 连接顶点的边 2 和 4

黑边的数量不能超过 5,所以输出 5.


示例输入 2

7 3
1 2
2 3
3 6

示例输出 2

20

示例输入 3

123123 0

示例输出 3

7579575003

小心溢出。