题目描述

给定一个 $n$ 个点，$m$ 条边的无向图，求问有多少对还未经连接的点对满足在连接它们后，该图为一个二分图。

注意这里点对是无序点对。

数据保证没有自环与重边。

输入格式

输入的第一行为 $n,m$。

然后总共 $m$ 行，每一行为一条无向边，连接 $u_i$ 和 $v_i$。

输出格式

一个数，为满足要求的点对数量。

5 4
4 2
3 1
5 2
3 2

2

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

数据范围

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