B - Triangle Toggle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

頂点に 1 から N の番号がついた N 頂点の完全グラフがあります。各辺は黒か白で塗られており、 i=1,2,\ldots,M に対し頂点 U_i と頂点 V_i を結ぶ辺は黒で、これら以外の辺は白で塗られています。

あなたは以下の操作を 0 回以上何回でも行うことができます。

  • 1\le a < b < c \le N を満たす整数の組 (a,b,c) を選び、以下の 3 本の辺のそれぞれの色を白ならば黒に、黒ならば白に塗り直す。
    • 頂点 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

以下のように 2 回の操作を行うことで、黒で塗られた辺の本数を 5 本にすることができます。

  • (a,b,c)=(1,3,4) を選ぶ。黒で塗られた辺は以下の 4 本になる。
    • 頂点 1 と頂点 2 を結ぶ辺
    • 頂点 1 と頂点 3 を結ぶ辺
    • 頂点 1 と頂点 4 を結ぶ辺
    • 頂点 3 と頂点 4 を結ぶ辺
  • (a,b,c)=(2,3,4) を選ぶ。黒で塗られた辺は以下の 5 本になる。
    • 頂点 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

オーバーフローに注意してください。

Score : 500 points

Problem Statement

There is a complete graph with N vertices numbered 1 to N. Each edge is colored black or white. For i=1,2,\ldots,M, the edge connecting vertices U_i and V_i is colored black, and all other edges are colored white.

You can perform the following operation zero or more times.

  • Choose a triple of integers (a,b,c) satisfying 1\le a < b < c \le N, and repaint each of the following three edges: white to black, black to white.
    • The edge connecting vertices a and b
    • The edge connecting vertices b and c
    • The edge connecting vertices a and c

Find the maximum number of edges that can be colored black when you perform operations appropriately.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Output the answer.

Sample Input 1

4 1
1 2

Sample Output 1

5

By performing two operations as follows, you can make the number of black edges 5.

  • Choose (a,b,c)=(1,3,4). Then, we have the following four black edges.
    • The edge connecting vertices 1 and 2
    • The edge connecting vertices 1 and 3
    • The edge connecting vertices 1 and 4
    • The edge connecting vertices 3 and 4
  • Choose (a,b,c)=(2,3,4). Then, we have the following five black edges.
    • The edge connecting vertices 1 and 2
    • The edge connecting vertices 1 and 3
    • The edge connecting vertices 1 and 4
    • The edge connecting vertices 2 and 3
    • The edge connecting vertices 2 and 4

You cannot make the number of black edges more than 5, so output 5.

Sample Input 2

7 3
1 2
2 3
3 6

Sample Output 2

20

Sample Input 3

123123 0

Sample Output 3

7579575003

Be careful about overflow.