You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

加边

题目描述

给定一个 $N$ 个点，$M$ 条边的无向图，求问有多少种添加一条边的方案，使得新图是一个二分图。

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

输入格式

第一行两个整数 $N,M$ ，接下来 $M$ 行每行两个整数 $u_i,v_i$ 表示图中的一条边。

输出格式

一个整数表示答案。

样例 #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

数据范围

对 $25\%$ 的数据， $N\ \leq\ 1000$ 。

对 $100\%$ 的数据， $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$

Sample Explanation 1

可以加的边为 $(1,4)$ 或 $(1,5)$ 。