Jaehyun a résolu un problème concernant la coupe maximale d'un graphe lors du camp d'hiver 2019 de Petrozavodsk, il a donc décidé de faire plaisir aux participants du camp d'entraînement de Petrozavodsk avec un autre problème de même nature.

Vous disposez d'un graphe simple et connexe $G = (V, E)$ avec $N$ sommets et $M$ arêtes. Trouvez le nombre de sous-ensembles d'arêtes $S \subseteq E$ tels que :

• La suppression des arêtes dans $S$ rend le graphe biparti.
• $|S| \leq 2$.
• Il n'existe aucun autre sous-ensemble $T \subseteq E$ tel que $|T| < |S|$ et que les deux premières conditions soient satisfaites.

Notez que $S$ peut être vide.

Entrée

La première ligne de l'entrée contient deux entiers $N$ et $M$ ($3 \leq N \leq 250\,000$, $N - 1 \leq M \leq 250\,000$).

Ensuite, $M$ lignes suivent. Chacune d'elles contient deux entiers séparés par un espace $u_i$ et $v_i$ ($1 \leq u_i, v_i \leq N$). Cela décrit une arête bidirectionnelle reliant le sommet $u_i$ au sommet $v_i$.

Il est garanti que le graphe donné ne contient ni boucles ni arêtes multiples, et que le graphe est connexe.

Sortie

Affichez le nombre de sous-ensembles d'arêtes qui satisfont les conditions données.

Exemples

Entrée 1

3 2
1 2
2 3

Sortie 1

1

Entrée 2

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

Sortie 2

3

Entrée 3

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

Sortie 3

0

Entrée 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

Sortie 4

2