Jaehyun 在 Petrozavodsk Winter 2019 營隊中解決了一個關於圖的最大割問題，因此他決定用另一個性質相同的問題來取悅 Petrozavodsk 訓練營的參與者。

給定一個包含 $N$ 個頂點和 $M$ 條邊的簡單連通圖 $G = (V, E)$。請找出滿足以下條件的邊子集 $S \subseteq E$ 的數量：

• 移除 $S$ 中的邊後，圖變為二分圖。
• $|S| \le 2$。
• 不存在其他子集 $T \subseteq E$ 滿足 $|T| < |S|$ 且同時滿足上述前兩個條件。

注意 $S$ 可以為空集。

輸入格式

第一行包含兩個整數 $N$ 和 $M$ ($3 \le N \le 250\,000$, $N - 1 \le M \le 250\,000$)。

接下來 $M$ 行，每行包含兩個以空格分隔的整數 $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