Дороги
Дороги
В Украине, как известно, много проблем. Одна из них — дороги. Вновь избранный президент Украины решил заняться строительством дорог. Его цель — построить некоторое дополнительное количество дорог между городами так, чтобы можно было проехать из любого города Украины в любой (возможно, через другие города, не обязательно напрямую). Естественно, при этом дополнительных дорог должно быть построено как можно меньше.
Будем считать, что все дороги в Украине двухсторонние (и уже имеющиеся, и те, что будут построены), то есть по ним возможно движение в обоих направлениях. Учтите, что между двумя городами может быть несколько дорог. Кроме того, могут существовать дороги, связывающие город с самим собой.
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ə
7 5 1 3 2 3 3 2 2 4 6 7
2