AT_abc282_d [ABC282D] Make Bipartite 2

题目描述

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

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

• 在图 $G$ 中，顶点 $u$ 和顶点 $v$ 之间不存在边。
• 在图 $G$ 中添加一条连接顶点 $u$ 和顶点 $v$ 的边后，所得的图仍然是二分图。

什么是二分图？无向图被称为二分图，当且仅当可以将所有顶点染成黑色或白色，使得不存在连接同色顶点的边。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

输出答案。

输入输出样例 #1

输入 #1

5 4
4 2
3 1
5 2
3 2

输出 #1

2

输入输出样例 #2

输入 #2

4 3
3 1
3 2
1 2

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min\{2 \times 10^5, N(N-1)/2\}$
• $1 \leq u_i, v_i \leq N$
• 图 $G$ 是简单图
• 所有输入均为整数

样例解释 1

满足题目条件的整数对 $(u, v)$ 有 $(1, 4)$ 和 $(1, 5)$ 共 $2$ 个，因此输出 $2$。对于其他的对，例如 $(1, 3)$，因为在图 $G$ 中顶点 $1$ 和顶点 $3$ 之间存在边，不满足条件；又如 $(4, 5)$，在图 $G$ 中添加连接顶点 $4$ 和顶点 $5$ 的边后，所得图不是二分图，因此也不满足条件。

样例解释 2

请注意，给定的图不一定是二分图，也不一定是连通图。

由 ChatGPT 4.1 翻译