eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Winter

Країна Ужляндія славиться своїми ідеальними дорогами, але навіть вони не витримали цьогорічної аномально холодної та сніжної зими. Деякі з доріг виявилися заблокованими для руху автомобілістів. Внаслідок цього порушився зв’язок між містами Ужляндії. Два міста країни вважаються з’єднаними, якщо можна дістатися з одного міста в інше, рухаючись не заблокованими дорогами, можливо, через інші міста. Сусідня братська держава відома на весь світ своїми унікальними обігрівачами. Керівництво країни вирішило надати Ужляндії гуманітарну допомогу. Було вирішено, що обігрівачі доставлятимуться на гвинтокрилі, а далі за допомогою вантажівок розвозитимуться по містах. Оскільки авіаційне паливо не дешеве, потрібно мінімізувати кількість приземлень гвинтокрила так, щоби кожне місто отримало необхідні обігрівачі. Будь ласка, якомога швидше порахуйте цю кількість і врятуйте мешканців Ужляндії. \textbf{Формат вхідних даних:} В першому рядку записано два числа \textit{\textbf{N}} і \textit{\textbf{M (1 ≤ N ≤ 100000,0 ≤ M ≤ 200000)}} -- кількість міст в Ужляндії та кількість не заблокованих доріг відповідно. В наступних \textit{\textbf{M}} рядках записано по два числа \textit{\textbf{i}} та \textit{\textbf{j (1 ≤ i, j ≤ N)}}, що значить дорога між містами з номерами \textit{\textbf{i}} та \textit{\textbf{j}} не заблокована. Міста в Ужляндії нумеруються в 1 до \textit{\textbf{N}}. \textbf{Формат вихідних даних:} В єдиному рядку виведіть мінімальну кількість приземлень гвинтокрила. \textit{\textbf{Пояснення до прикладу:}} Міста 1, 2 та 3 з’єднані між собою, а тому щоби забезпечити їх обігрівачами, необхідно здійснити одне приземлення в одному з цих міст, далі обігрівачі доставлять вантажівками. Міста 4 та 5 зв’язані між собою, тому треба ще одне приземлення. І нарешті місто 6, яке ізольоване від інших, щоби доставити обігрівачі в це місто, треба окреме приземлення гвинтокрила. Всього виходить 3 приземлення.
Лимит времени 0.5 секунд
Лимит использования памяти 64 MiB
Входные данные #1
6 4
3 1
1 2
5 4
2 3
Выходные данные #1
3
Источник ІІІ етап Всеукраїнської олімпіади 2014 р.