Make Bipartite 2

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图 $G$（简单图不包含自环或重边）。 对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 输出满足 $1 \leq u \lt v \leq N$ 且下列两个条件都成立的整数对 $(u, v)$ 的数量。

图 $G$ 中不存在一条连接顶点 $u$ 和顶点 $v$ 的边。 在图 $G$ 中加入一条连接顶点 $u$ 和顶点 $v$ 的边后，所得的图是二分图。

输入格式

输入按下列格式从标准输入给出： $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

输出答案。

5 4
4 2
3 1
5 2
3 2

2

4 3
3 1
3 2
1 2

0

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

9

提示

$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$ 是简单图。 输入中的所有数值均为整数。有两个满足题目条件的整数对 $(u, v)$：$(1, 4)$ 和 $(1, 5)$。因此应输出 $2$.
其他的对不满足条件。例如，对于 $(1, 3)$，图 $G$ 中存在连接顶点 $1$ 和顶点 $3$ 的边；对于 $(4, 5)$，在图 $G$ 中加入连接顶点 $4$ 和顶点 $5$ 的边后，所得的图不是二分图。
注意，给定的图可能不是二分图也可能不是连通的。

标签: AtCoder|abc282D

来源

AtCoder|abc282D