AT_code_festival_2017_qualb_c 3 Steps

[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 $

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

### 制約 - $ 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 $ の間に辺を追加する。