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