题目描述

$N$ 個の頂点と $M$ 本の辺からなる単純な（すなわち、自己ループも多重辺も含まない）無向グラフ $G$ が与えられます。 $i\ =\ 1,\ 2,\ \ldots,\ M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。

$1\ \leq\ u\ \lt\ v\ \leq\ N$ を満たす整数の組 $(u,\ v)$ であって、下記の $2$ つの条件をともに満たすものの個数を出力してください。

• グラフ $G$ において、頂点 $u$ と頂点 $v$ を結ぶ辺は存在しない。

• グラフ $G$ に、頂点 $u$ と頂点 $v$ を結ぶ辺を追加して得られるグラフは、二部グラフである。

  二部グラフとは？無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。

• 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

答えを出力せよ。

题目大意

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

注意这里点对 $(u,v)$ 和点对 $(v,u)$ 是同一对点对。

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

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$
• グラフ $G$ は単純
• 入力はすべて整数

Sample Explanation 1

問題文中の条件を満たす整数の組 $(u,\ v)$ は、$(1,\ 4)$ と $(1,\ 5)$ の $2$ つです。よって、$2$ を出力します。 他の組については、例えば、$(1,\ 3)$ はグラフ $G$ において頂点 $1$ と頂点 $3$ を結ぶ辺が存在することから、 $(4,\ 5)$ はグラフ $G$ に頂点 $4$ と頂点 $5$ を結ぶ辺を追加して得られるグラフが二部グラフではないことから、 それぞれ問題文中の条件を満たしません。

Sample Explanation 2

与えられるグラフが二部グラフであったり連結であるとは限らないことに注意してください。