问题描述

有一个完全图（complete graph），顶点编号为 $1$ 到 $N$。每条边被着色为黑色或白色。初始时给出 $M$ 条黑边：对于 $i=1,2,\dots,M$，连接顶点 $U_i$ 和 $V_i$ 的边被着成黑色，其余边为白色。

你可以重复执行以下操作任意次（也可以不执行）：

• 选择一个三元组顶点 $(a,b,c)$ 满足 $1\le a<b<c\le N$，并将下面三条边的颜色同时取反（白变黑，黑变白）：

  • 边 $(a,b)$
  • 边 $(b,c)$
  • 边 $(a,c)$

经过若干次操作后，问能使得黑色边的最多数量为多少？

输入格式

• 第一行包含两个整数 $N$ 和 $M$。
• 接下来 $M$ 行，每行两个整数 $U_i\ V_i$，表示初始时边 $(U_i,V_i)$ 为黑色。
• 保证 $1\le U_i<V_i\le N$，且没有重边。

输出格式

输出一个整数，为能得到的最多黑边数。

样例输入 1

4 1
1 2

样例输出 1

5

样例输入 2

7 3
1 2
2 3
3 6

样例输出 2

20

样例输入 3

123123 0

样例输出 3

7579575083

说明

样例 $1$ 解释

可以按如下两次操作使黑边数为 $5$：

• 选择 $(a,b,c)=(1,3,4)$，此时黑边有：$(1,2),(1,3),(1,4),(3,4)$（共 $4$ 条）。
• 选择 $(a,b,c)=(2,3,4)$，此时黑边有：$(1,2),(1,3),(1,4),(2,3),(2,4)$（共 $5$ 条）。

无法再增大到超过 $5$，所以输出 $5$。

数据范围

• $3\le N\le 2\times 10^5$。
• $0\le M\le 2\times 10^5$。
• 所有输入值为整数。
• 边 $(U_i,V_i)$ 在输入中不重复。