← 返回题目列表

AtCoder · abc282_d

G. 制作二分 2

中文机器翻译题面 查看原题

分数: 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