102823: [AtCoder]ABC282 D - Make Bipartite 2

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.

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

问题描述

给你一个包含 $N$ 个顶点和 $M$ 条边的简单无向图（简单图不包含自环或多边形）。 对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

打印满足以下两个条件的整数对 $(u, v)$ 的数量。

• 图 $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$。
其他对不满足条件。例如，对于 $(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