У Farmer John $N$ пастбищ ($1 \leq N \leq 50,000$), с номерами $1...N$, соединённых $M$ двусторонними дорогами ($1 \leq M \leq 100,000$). Дорога $i$ соединяет $A_i$ ($1 \leq A_i \leq N$) и $B_i$ ($1 \leq B_i \leq N$), причём $A_i != B_i$. Одну пару могут соединять две дороги.

Bessie украшает пастбища ко дню рождения FJ. На каждом хочет большой знак с '$F$' или '$J$', но, чтобы не путать FJ, соединённые дорогой пастбища должны иметь разные буквы.

Компания берёт за '$F$' больше, чем за '$J$', поэтому Bessie максимизирует число '$J$'. Найдите его или выведите -1, если допустимого размещения нет.

Входные данные

• Строка 1: целые $N$ и $M$.
• Строки $2..M+1$: целые $A_i$ и $B_i$, задающие двустороннюю дорогу между $A_i$ и $B_i$.

Выходные данные

• Строка 1: целое, максимальное число знаков '$J$'. Если допустимого решения нет, выведите -1.

Примеры

Входные данные 1

4 4
1 2
2 3
3 4
4 1

Выходные данные 1

2

Примечание

Пастбища и дороги образуют вершины и стороны квадрата.

Bessie может поставить '$J$' на пастбищах 1 и 3 либо 2 и 4.

Автор задачи: Kalki Seksaria, 2014