D - Make Bipartite 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個の頂点と M 本の辺からなる単純な（すなわち、自己ループも多重辺も含まない）無向グラフ G が与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結びます。

1 \leq u \lt v \leq N を満たす整数の組 (u, v) であって、下記の 2 つの条件をともに満たすものの個数を出力してください。

  • グラフ G において、頂点 u と頂点 v を結ぶ辺は存在しない。
  • グラフ G に、頂点 u と頂点 v を結ぶ辺を追加して得られるグラフは、二部グラフである。
二部グラフとは？

無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。

  • 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
  • 1 \leq u_i, v_i \leq N
  • グラフ G は単純
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

5 4
4 2
3 1
5 2
3 2

出力例 1

2

問題文中の条件を満たす整数の組 (u, v) は、(1, 4) と (1, 5) の 2 つです。よって、2 を出力します。
他の組については、例えば、(1, 3) はグラフ G において頂点 1 と頂点 3 を結ぶ辺が存在することから、 (4, 5) はグラフ G に頂点 4 と頂点 5 を結ぶ辺を追加して得られるグラフが二部グラフではないことから、 それぞれ問題文中の条件を満たしません。

入力例 2

4 3
3 1
3 2
1 2

出力例 2

0

与えられるグラフが二部グラフであったり連結であるとは限らないことに注意してください。

入力例 3

9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8

出力例 3

9

Score : 400 points

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

  • The graph G does not have an edge connecting vertex u and vertex v.
  • Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.
What is a bipartite graph?

An undirected graph is said to be bipartite if and only if one can paint each vertex black or white to satisfy the following condition.

  • No edge connects vertices painted in the same color.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
  • 1 \leq u_i, v_i \leq N
  • The graph G is simple.
  • All values in the input 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

Print the answer.

Sample Input 1

5 4
4 2
3 1
5 2
3 2

Sample Output 1

2

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

4 3
3 1
3 2
1 2

Sample Output 2

0

Note that the given graph may not be bipartite or connected.

Sample Input 3

9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8

Sample Output 3

9