Задача C. День бульдозериста ≡

Автор:И. Олейников, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

Город представляет из себя N площадей и M отрезков улиц между ними. Бульдозер может начинать расчистку с любой площади, и не должен ехать по уже расчищенным улицам (но может проезжать уже расчищенные площади). Если бульдозер оказывается на площади, все улицы которой уже расчищены, бульдозерист считает свой рабочий день законченным, бросает бульдозер и уходит.

Требуется определить минимально необходимое число бульдозеров.

Формат входного файла

Входной файл содержит числа N и M за которыми идут M пар чисел ai bi — номера площадей, соединенных i-й улицей (по улице, соединяющей площади ai и bi, можно проехать либо из ai и bi, либо из bi в ai). Две площади могут быть соединены больше чем одной улицей.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 40000, 1 ≤ M ≤ 40000, 1 ≤ ai, bi ≤ N

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
1 2 
2 3 
3 1
 
1
2 
5 2 
1 2 
3 4
 
3
0.039s 0.007s 15