JaehyunはPetrozavodsk Winter 2019キャンプでグラフの最大カットに関する問題を解いたため、Petrozavodskトレーニングキャンプの参加者を楽しませるために、同じ性質を持つ別の問題を作成することにしました。

$N$ 個の頂点と $M$ 個の辺を持つ単純連結グラフ $G = (V, E)$ が与えられます。以下の条件を満たす辺の集合 $S \subseteq E$ の個数を求めてください。

• $S$ に含まれる辺を取り除くと、グラフは二部グラフになる。
• $|S| \le 2$。
• $|T| < |S|$ かつ上記の2つの条件を満たすような、他の辺の集合 $T \subseteq E$ は存在しない。

$S$ は空集合であってもよいことに注意してください。

入力

入力の最初の行には、2つの整数 $N$ と $M$ ($3 \le N \le 250\,000$, $N - 1 \le M \le 250\,000$) が含まれます。

続く $M$ 行には、それぞれ2つの空白区切りの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le N$) が含まれます。これは、頂点 $u_i$ と頂点 $v_i$ を結ぶ無向辺を表します。

与えられるグラフにはループや多重辺は存在せず、グラフは連結であることが保証されています。

出力

与えられた条件を満たす辺の集合の個数を出力してください。

入出力例

入力 1

3 2
1 2
2 3

出力 1

1

入力 2

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

出力 2

3

入力 3

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

出力 3

0

入力 4

12 16
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 5
1 5
2 7
3 9
4 11

出力 4

2