题目描述

りんごさんは $N$ 頂点 の連結な無向グラフを持っています。 このグラフにはすでに $M$ 本の辺があり、$i$ 本目の辺は頂点 $A_i$ と頂点 $B_i$ を繋いでいます。

りんごさんは以下の操作を行うことで、辺を追加しようと思っています。

• 操作：頂点 $u$ から辺をちょうど $3$ 本辿ることによって頂点 $v$ に辿り着けるような $u,v\ (u\ \neq\ v)$ をとり、頂点 $u$ と頂点 $v$ の間に辺を追加する。ただし、すでに頂点 $u$ と頂点 $v$ の間に辺が存在する場合は辺を追加することはできない。

りんごさんが追加できる辺の本数の最大値を求めて下さい。

输入格式

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$

输出格式

追加できる辺の本数の最大値を出力せよ。

题目大意

给你一个 $n$ 个点 $m$ 条边的无向联通图，进行以下操作：

如果存在两个点 $u$ 和 $v$，使得从 $u$ 走三步能恰好到达$v$，那么在 $u$ 和 $v$ 之间连接一条边。

重复这个操作直到不能再连接新的边，问最后连接多少条边？

$n, m \leq 100000$

6 5
1 2
2 3
3 4
4 5
5 6

4

5 5
1 2
2 3
3 1
5 4
5 1

5

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ 10^5$
• $1\ \leq\ A_i,B_i\ \leq\ N$
• 多重辺や自己ループは存在しない
• 与えられるグラフは連結である

Sample Explanation 1

下の図のように辺を追加していくと $4$ 本の辺を追加することができ、これ以上辺を追加することはできません。 

Sample Explanation 2

例えば、以下のような順番で辺を追加することによって $5$ 本の辺を追加することができます。 - 頂点 $5$ と頂点 $3$ の間に辺を追加する。 - 頂点 $5$ と頂点 $2$ の間に辺を追加する。 - 頂点 $4$ と頂点 $1$ の間に辺を追加する。 - 頂点 $4$ と頂点 $2$ の間に辺を追加する。 - 頂点 $4$ と頂点 $3$ の間に辺を追加する。