Единая сеть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В новом регионе Сэм обнаружил $$$n$$$ городов, которые нужно объединить в сеть. Города соединены $$$m$$$ двусторонними дорогами. Причём, по дорогам можно добраться от любого города до любого другого. Также, Сэм обнаружил, что каждая дорога принадлежит максимум одному простому циклу. Иными словами, граф городов образует рёберный кактус.

Для того, чтобы объединить города в сеть, Сэму нужно поставить в каждом городе передатчик одного из трёх типов. При этом, в любых двух городах, соединённых дорогой, типы передатчиков должны различаться. Передатчики третьего типа являются очень дорогими, поэтому Сэм хочет использовать их как можно меньше. Помогите ему определить минимальное количество передатчиков третьего типа, которых нужно использовать, чтобы объединить все города в сеть, либо сообщите, что это невозможно при любом количестве передатчиков.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — количество городов и дорог ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 150\,000$$$).

В следующих $$$m$$$ строках дано по два целых числа $$$a_i$$$ и $$$b_i$$$ — номера городов, соединённых $$$i$$$-й дорогой ($$$1 \le a_i, b_i \le n$$$; $$$a_i \neq b_i$$$). Гарантируется, что в графе нет петель и кратных ребер, граф связен и является рёберным кактусом.

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

Если объединить города в сеть невозможно, выведите «-1», иначе выведите минимальное количество передатчиков третьего типа, которых нужно для этого использовать.

Примеры

Входные данные
7 9
1 2
2 3
3 1
2 4
4 5
5 2
3 6
6 7
7 3
Выходные данные
2
Входные данные
15 18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 3
2 9
9 10
10 11
11 12
12 13
13 10
2 14
14 9
9 15
15 10
Выходные данные
1

Примечание

Пояснение к первому тесту, один из способов расставить передатчики оптимальным образом (передатчики третьего типа изображены красным цветом):

Пояснение ко второму тесту: