П'ятниця, 11.07.2025, 14:42
Гость

Мішатронік

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Хто ви?

Всього відповідей: 10
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0


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

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

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

Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.

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

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

Примеры
входные данные
4 5
1 2
1 3
2 3
3 4
4 1
выходные данные
4

 

 

Форма входа
Пошук
Друзі сайту
Календар
«  Липень 2025  »
ПнВтСрЧтПтСбНд
 123456
78910111213
14151617181920
21222324252627
28293031

Єдина Країна! Единая Страна!