当前没有测试数据。

D - 使其成为二分图 2

得分：$400$ 分

问题描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图 $G$ (一个简单图不包含自环或者重边)。

输出满足下列条件的整数对 $(u, v)$ 的数量，其中 $1 \leq u \lt v \leq N$：

• 图 $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$

输出

输出答案。

5 4
4 2
3 1
5 2
3 2

2

满足问题描述中条件的整数对 $(u, v)$ 有两个：$(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