День бульдозериста
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В некотором городе однажды выпал снег. Неожиданно выяснилось, что вся снегоуборочная техника
находится на ремонте, и для расчистки улиц было решено привлечь тяжёлые гусеничные бульдозеры.
Задача осложняется тем, что асфальтовое покрытие улиц может выдержать только один проход
такого бульдозера.
Город представляет из себя N площадей и M отрезков улиц между ними.
Бульдозер может начинать
расчистку с любой площади, и не должен ехать по уже расчищенным улицам (но может
проезжать уже расчищенные площади). Если бульдозер оказывается на площади,
все улицы которой уже расчищены, бульдозерист считает свой рабочий день законченным,
бросает бульдозер и уходит.
Требуется определить минимально необходимое число бульдозеров.
Ввод
Входной файл содержит числа N и M за которыми идут
M пар чисел ai bi –- номера площадей,
соединенных i-й улицей (по улице, соединяющей площади ai и bi,
можно проехать
либо из ai и bi,
либо из bi в ai).
Две площади могут быть соединены больше чем одной улицей.
Вывод
В выходной файл должно быть выведено единственное число – наименьшее количество бульдозеров,
необходимых для расчистки всех дорог и площадей города по указанным выше правилам.
Ограничения
2 ,
1\ ≤\ M\ ≤\ 40\ 000,
1\ ≤\ a_i,\ b_i\ ≤\ N
Пример ввода 1
3 3
1 2
2 3
3 1
Пример ввода 2
5 2
1 2
3 4
Источник: И. Олейников, А. Кленин, ДВГУ, Весенний турнир, 2005