e-olymp
Соревнования

ADA Classes - Graph Applications

Дороги

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

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

Входные данные

Первая строка содержит два натуральных числа n и m (1n, m10000) - количество городов и количество уже существующих дорог. Следующие m строк содержат по два целых числа ai и bi (1ai, bin) - номера городов, которые соединены уже существующей дорогой.

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
7 5
1 3
2 3
3 2
2 4
6 7
Выходные данные #1
2
Источник Крым 2010