分数: 400 点
问题陈述
给你一个简单的无向图 G 与 N 顶点和 M 边(简单图不包含自环或多边)。 对于 i = 1, 2, \ldots, M, i第一条边连接顶点 u_i 和顶点 v_i.
打印整数对的数量 (u, v) 满足 1 \leq u \lt v \leq N 以及以下两个条件。
- 图表 G 没有连接顶点的边 u 和顶点 v.
- 添加连接顶点的边 图中的 u 和顶点 v 在图中 G 生成二分图。
什么是二分图?
无向图据说是 双方 当且仅当可以将每个顶点绘制为黑色或白色以满足以下条件。
- 没有边连接涂有相同颜色的顶点。
约束
- 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),添加连接顶点的边 4 和顶点 5 在图中 G 不会产生二部图。
示例输入 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