Farmer John ma $N$ pastwisk ($1 \leq N \leq 50,000$), numerowanych $1...N$, połączonych $M$ dwukierunkowymi drogami ($1 \leq M \leq 100,000$). Droga $i$ łączy $A_i$ ($1 \leq A_i \leq N$) z $B_i$ ($1 \leq B_i \leq N$), gdzie $A_i != B_i$. Dwie drogi mogą łączyć tę samą parę.

Bessie dekoruje na urodziny FJ. Chce na każdym pastwisku dużą tablicę '$F$' albo '$J$', ale aby go nie mylić, pastwiska połączone drogą muszą mieć różne litery.

Firma pobiera za '$F$' więcej niż za '$J$', więc Bessie maksymalizuje liczbę '$J$'. Znajdź ją albo wypisz -1, jeśli poprawne rozmieszczenie nie istnieje.

Wejście

• Wiersz 1: całkowite $N$ i $M$.
• Wiersze $2..M+1$: całkowite $A_i$ i $B_i$, wskazujące dwukierunkową drogę między $A_i$ i $B_i$.

Wyjście

• Wiersz 1: liczba całkowita, maksymalna liczba tablic '$J$'. Jeśli poprawne rozwiązanie nie istnieje, wypisz -1.

Przykład

Wejście 1

4 4
1 2
2 3
3 4
4 1

Wyjście 1

2

Uwagi

Pastwiska i drogi tworzą wierzchołki i boki kwadratu.

Bessie może umieścić '$J$' na pastwiskach 1 i 3 albo 2 i 4.

Autor zadania: Kalki Seksaria, 2014