Jaehyun rozwiązał zadanie dotyczące maksymalnego cięcia w grafie podczas obozu Petrozavodsk Winter 2019, więc postanowił sprawić przyjemność uczestnikom obozu treningowego w Pietrozawodsku kolejnym zadaniem o podobnym charakterze.

Dany jest prosty graf spójny $G = (V, E)$ o $N$ wierzchołkach i $M$ krawędziach. Znajdź liczbę podzbiorów krawędzi $S \subseteq E$ takich, że:

• Usunięcie krawędzi ze zbioru $S$ sprawia, że graf staje się dwudzielny.
• $|S| \leq 2$.
• Nie istnieje żaden inny podzbiór $T \subseteq E$ taki, że $|T| < |S|$ i spełnione są dwa powyższe warunki.

Zauważ, że $S$ może być zbiorem pustym.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $N$ oraz $M$ ($3 \leq N \leq 250\,000$, $N - 1 \leq M \leq 250\,000$).

Następnie następuje $M$ linii. Każda z nich zawiera dwie oddzielone spacją liczby całkowite $u_i$ oraz $v_i$ ($1 \leq u_i, v_i \leq N$). Opisują one krawędź dwukierunkową łączącą wierzchołek $u_i$ z wierzchołkiem $v_i$.

Gwarantuje się, że dany graf nie posiada pętli ani krawędzi wielokrotnych, a graf jest spójny.

Wyjście

Wypisz liczbę podzbiorów krawędzi, które spełniają podane warunki.

Przykład

Wejście 1

3 2
1 2
2 3

Wyjście 1

1

Wejście 2

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

Wyjście 2

3

Wejście 3

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

Wyjście 3

0

Wejście 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

Wyjście 4

2