分数: 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
小心溢出。