eolymp
bolt
Try our new interface for solving problems
Məsələlər

Дороги

Дороги

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

В Украине, как известно, много проблем. Одна из них — дороги. Вновь избранный президент Украины решил заняться строительством дорог. Его цель — построить некоторое дополнительное количество дорог между городами так, чтобы можно было проехать из любого города Украины в любой (возможно, через другие города, не обязательно напрямую). Естественно, при этом дополнительных дорог должно быть построено как можно меньше.

Будем считать, что все дороги в Украине двухсторонние (и уже имеющиеся, и те, что будут построены), то есть по ним возможно движение в обоих направлениях. Учтите, что между двумя городами может быть несколько дорог. Кроме того, могут существовать дороги, связывающие город с самим собой.

Giriş verilənləri

Первая строка содержит два натуральных числа n и m\:(1 \le n, m \le 10000) — количество городов и количество уже существующих дорог. Следующие m строк содержат по два целых числа a_i и b_i\:(1 \le a_i, b_i \le n) — номера городов, которые соединены уже существующей дорогой.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
7 5
1 3
2 3
3 2
2 4
6 7
Çıxış verilənləri #1
2
Mənbə Крым 2010