题目描述

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

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

• 图 $G$ 中没有连接顶点 $u$ 和顶点 $v$ 的边。
• 向图 $G$ 中添加连接顶点 $u$ 和顶点 $v$ 的边会得到一个二分图。

什么是二分图？

一个无向图被称为二分图，当且仅当可以将每个顶点涂成黑色或白色，以满足以下条件：

• 没有连接相同颜色的顶点的边。

约束条件

• $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$ 是简单图。
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

$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)$，向图 $G$ 中添加连接顶点 $4$ 和顶点 $5$ 的边不会得到一个二分图。

示例输入 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