3 Steps

给你一个 $n$ 个点 $m$ 条边的无向联通图，进行以下操作： 如果存在两个点 $u$ 和 $v$，使得从 $u$ 走三步能恰好到达$v$，那么在 $u$ 和 $v$ 之间连接一条边。 重复这个操作直到不能再连接新的边，问最后连接多少条边？ $n, m \leq 100000$

[problemUrl]: https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c りんごさんは $ 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 $

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

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 $ 本の辺を追加することができ、これ以上辺を追加することはできません。 !\[\](https://img.atcoder.jp/code-festival-2017-qualb/6e99dccc06ac8b14d9ca2e297524bc0c.png) ### Sample Explanation 2 例えば、以下のような順番で辺を追加することによって $ 5 $ 本の辺を追加することができます。 - 頂点 $ 5 $ と頂点 $ 3 $ の間に辺を追加する。 - 頂点 $ 5 $ と頂点 $ 2 $ の間に辺を追加する。 - 頂点 $ 4 $ と頂点 $ 1 $ の間に辺を追加する。 - 頂点 $ 4 $ と頂点 $ 2 $ の間に辺を追加する。 - 頂点 $ 4 $ と頂点 $ 3 $ の間に辺を追加する。