Məsələlər
Дороги
Дороги
В Украине, как известно, много проблем. Одна из них --- дороги. Вновь избранный президент Украины решил заняться строительством дорог. Его цель --- построить некоторое дополнительное количество дорог между городами так, чтобы можно было проехать из любого города Украины в любой (возможно, через другие города, не обязательно напрямую). Естественно, при этом дополнительных дорог должно быть построено как можно меньше.
Будем считать, что все дороги в Украине двухсторонние (и уже имеющиеся, и те, что будут построены), то есть по ним возможно движение в обоих направлениях. Учтите, что между двумя городами может быть несколько дорог. Кроме того, могут существовать дороги, связывающие город с самим собой.
\InputFile
Первая строка содержит два натуральных числа $n$ и $m\:(1 \le n, m \le 10000)$ --- количество городов и количество уже существующих дорог. Следующие $m$ строк содержат по два целых числа $a_i$ и $b_i\:(1 \le a_i, b_i \le n)$ --- номера городов, которые соединены уже существующей дорогой.
\OutputFile
Вывести минимальное количество дорог, которое необходимо построить, чтобы существовал путь из любого города в любой.
\includegraphics{https://static.e-olymp.com/content/7d/7db37796051b373cae229dbd30afbc78215ae345.gif}
Giriş verilənləri #1
7 5 1 3 2 3 3 2 2 4 6 7
Çıxış verilənləri #1
2