Farmer John possède $N$ pâturages ($1 \leq N \leq 50,000$), numérotés $1...N$, reliés par $M$ chemins bidirectionnels ($1 \leq M \leq 100,000$). Le chemin $i$ relie $A_i$ ($1 \leq A_i \leq N$) à $B_i$ ($1 \leq B_i \leq N$), avec $A_i != B_i$. Deux chemins peuvent relier la même paire.

Bessie décore pour l'anniversaire de FJ. Elle veut dans chaque pâturage un grand panneau '$F$' ou '$J$', mais, pour éviter de troubler FJ, les pâturages reliés par un chemin doivent avoir des lettres différentes.

Le fabricant facture '$F$' plus cher que '$J$', donc elle maximise le nombre de '$J$'. Trouvez ce nombre ou affichez -1 si aucune disposition valide n'existe.

Entrée

• Ligne 1 : entiers $N$ et $M$.
• Lignes $2..M+1$ : entiers $A_i$ et $B_i$, indiquant un chemin bidirectionnel entre $A_i$ et $B_i$.

Sortie

• Ligne 1 : entier indiquant le maximum de panneaux '$J$'. Si aucune solution valide n'existe, affichez -1.

Exemples

Entrée 1

4 4
1 2
2 3
3 4
4 1

Sortie 1

2

Remarque

Les pâturages et chemins forment les sommets et côtés d'un carré.

Bessie peut choisir les pâturages 1 et 3 pour '$J$', ou bien 2 et 4.

Auteur du problème : Kalki Seksaria, 2014