C. Тропинки и полянки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася пришел погулять в парк. В парке есть n полянок пронумерованных от 1 до n. Между полянками есть m тропинок. Тропинки пронумерованы от 1 до m, причем i-ая тропинка соединяет полянки номер xi и yi. Номера соединяемых полянок могут совпадать (xi = yi) — это значит, что тропинка ведет с какой-то полянки на нее же. Также между двумя полянками может быть несколько непересекающихся тропинок.

Вася стоит на полянке номер 1, он хочет прогуляться по всем тропинкам парка ровно один раз, так чтобы в итоге вернуться на полянку номер 1. К сожалению, Вася не знает возможна такая прогулка или нет. Помогите Васе, определите возможна такая прогулка или нет. Если такая прогулка невозможна, найдите, какое минимальное количество тропинок придется дополнительно проложить в парке, чтобы описанная прогулка стала возможной.

Переходить с тропинки на тропинку Вася может только на полянках. По тропинкам можно двигаться в обоих направлениях. Если Вася зашел на тропинку, соединяющую полянки a и b, со стороны полянки a, то он обязан выйти с этой тропинки со стороны полянки b.

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

В первой строке записано два целых числа n и m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106) — количество полянок в парке и количество тропинок в парке соответственно. В следующих m строках задано описание тропинок. В i-й строке задано описание i-й тропинки — два числа, записанных через пробел, xi, yi (1 ≤ xi, yi ≤ n) — номера полянок, которые эта тропинка соединяет.

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

Выведите одно число — ответ на задачу. Если прогулка Васи возможна без строительства дополнительных тропинок выведите 0, иначе выведите минимальное количество тропинок, которые придется дополнительно проложить в парке, чтобы описанная прогулка стала возможной.

Примеры
Входные данные
3 3
1 2
2 3
3 1
Выходные данные
0
Входные данные
2 5
1 1
1 2
1 2
2 2
1 2
Выходные данные
1
Примечание

В первом тестовом примере описанная прогулка возможна и без постройки дополнительных тропинок. Например, сначала можно пройти по первой тропинке, потом по второй и, наконец, по третьей.

Во втором тестовом примере описанная прогулка невозможна без постройки дополнительных тропинок. Чтобы прогулка стала возможной, достаточно построить одну тропинку между полянками номер один и два.