Джехён решил задачу о максимальном разрезе графа в лагере Petrozavodsk Winter 2019, поэтому он решил порадовать участников тренировочного лагеря в Петрозаводске еще одной задачей того же рода.

Дан простой связный граф $G = (V, E)$ с $N$ вершинами и $M$ ребрами. Найдите количество подмножеств ребер $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

Примеры 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