构造二分图 2

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单无向图 $G$(简单图不包含自环和重边)。 对 $i = 1, 2, \ldots, M$,第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

求满足 $1 \le u \lt v \le 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

满足题目条件的整数对有 $(1, 4)$ 和 $(1, 5)$ 两组,因此应输出 $2$。

其他整数对不满足条件。例如,对 $(1, 3)$,图 $G$ 中存在连接顶点 $1$ 和顶点 $3$ 的边;对 $(4, 5)$,在图 $G$ 中添加连接顶点 $4$ 和顶点 $5$ 的边后,得到的图不是二分图。

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 \le N \le 2 \times 10^5$
• $0 \le M \le \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace$
• $1 \le u_i, v_i \le N$
• 图 $G$ 是简单图。
• 输入中的所有值都是整数。