配点 : $500$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_M$ $B_M$

出力

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

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

4

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

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

5

例えば、以下のような順番で辺を追加することによって $5$ 本の辺を追加することができます。

• 頂点 $5$ と頂点 $3$ の間に辺を追加する。
• 頂点 $5$ と頂点 $2$ の間に辺を追加する。
• 頂点 $4$ と頂点 $1$ の間に辺を追加する。
• 頂点 $4$ と頂点 $2$ の間に辺を追加する。
• 頂点 $4$ と頂点 $3$ の間に辺を追加する。