题目描述

Jaehyun 曾经在训练营中解决过一个与图的最大割有关的问题。为了让大家继续练习类似的图论技巧，他又准备了一个关于“让图变成二分图”的问题。

给定一张简单连通无向图

其中有 $N$ 个顶点和 $M$ 条边。你需要统计有多少个边集 $S\subseteq E$ 满足以下条件：

1. 删除 $S$ 中的所有边后，图变成二分图；
2. $|S|\le 2$；
3. 不存在另一个边集 $T\subseteq E$，使得 $|T|<|S|$，并且 $T$ 也满足前两个条件。

注意，$S$ 可以为空集。

也就是说，你需要统计所有大小不超过 $2$ 的、且在边数意义下最小的二分图修复方案。

输入格式

第一行包含两个整数 $N,M$，表示顶点数和边数。

接下来 $M$ 行，每行包含两个整数 $u_i,v_i$，表示一条连接 $u_i$ 和 $v_i$ 的无向边。

保证输入图没有自环和重边，并且图连通。

输出格式

输出一个整数，表示满足条件的边集 $S$ 的数量。

数据范围

• $3\le N\le 250000$；
• $N-1\le M\le 250000$；
• $1\le u_i,v_i\le N$。

样例 1

输入

3 2
1 2
2 3

输出

1

样例 2

输入

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

输出

3

样例 3

输入

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

输出

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

输出

2