Jaehyun resolvió un problema sobre el corte máximo de un grafo en el campamento de invierno de Petrozavodsk de 2019, por lo que decidió complacer a los participantes del campamento de entrenamiento de Petrozavodsk con otro problema de la misma naturaleza.

Se le da un grafo simple y conexo $G = (V, E)$ con $N$ vértices y $M$ aristas. Encuentre el número de subconjuntos de aristas $S \subseteq E$ tales que:

• La eliminación de las aristas en $S$ hace que el grafo sea bipartito.
• $|S| \leq 2$.
• No existe ningún otro subconjunto $T \subseteq E$ tal que $|T| < |S|$ y se cumplan las dos primeras condiciones.

Tenga en cuenta que $S$ puede estar vacío.

Entrada

La primera línea de la entrada contiene dos enteros $N$ y $M$ ($3 \leq N \leq 250\,000$, $N - 1 \leq M \leq 250\,000$).

Luego siguen $M$ líneas. Cada una de ellas contiene dos enteros separados por un espacio $u_i$ y $v_i$ ($1 \leq u_i, v_i \leq N$). Describe una arista bidireccional que conecta el vértice $u_i$ y el vértice $v_i$.

Se garantiza que el grafo dado no tiene bucles ni aristas múltiples, y que el grafo es conexo.

Salida

Imprima el número de subconjuntos de aristas que satisfacen las condiciones dadas.

Ejemplos

Entrada 1

3 2
1 2
2 3

Salida 1

1

Entrada 2

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

Salida 2

3

Entrada 3

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

Salida 3

0

Entrada 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

Salida 4

2