Farmer John ha $N$ pascoli ($1 \leq N \leq 50,000$), numerati $1...N$, collegati da $M$ sentieri bidirezionali ($1 \leq M \leq 100,000$). Il sentiero $i$ collega $A_i$ ($1 \leq A_i \leq N$) e $B_i$ ($1 \leq B_i \leq N$), con $A_i != B_i$. Due sentieri possono collegare la stessa coppia.

Bessie decora per il compleanno di FJ. Vuole in ogni pascolo un grande cartello '$F$' o '$J$', ma per non confonderlo, pascoli collegati da un sentiero devono avere lettere diverse.

L'azienda fa pagare '$F$' più di '$J$', quindi vuole massimizzare i '$J$'. Trova il numero oppure stampa -1 se non esiste disposizione valida.

Input

• Riga 1: interi $N$ e $M$.
• Righe $2..M+1$: interi $A_i$ e $B_i$, indicando un sentiero bidirezionale tra $A_i$ e $B_i$.

Output

• Riga 1: intero con il massimo di cartelli '$J$'. Se non esiste soluzione valida, stampa -1.

Esempi

Input 1

4 4
1 2
2 3
3 4
4 1

Output 1

2

Spiegazione

Pascoli e sentieri formano i vertici e lati di un quadrato.

Bessie può mettere '$J$' nei pascoli 1 e 3, oppure 2 e 4.

Autore del problema: Kalki Seksaria, 2014