Задача №1362. Острова
Одно разбросанное на островах Океании государство решило создать сеть автомобильных дорог (вернее, мостов). По каждому мосту можно перемещаться в обе стороны. Был разработан план очередности строительства мостов и известно, что после постройки всех мостов можно будет проехать по ним с каждого острова на каждый (возможно, через некоторые промежуточные острова).
Однако, этот момент может наступить до того, как будут построены все мосты. Ваша задача состоит в нахождении такого минимального количества мостов, после постройки которого (в порядке строительства по плану) можно будет попасть с любого острова на любой другой.
Первая строка содержит два числа: N - число островов (1 ≤ N ≤ 100 000) и M – количество мостов в плане (1 ≤ M ≤ 200 000). В каждой следующей строке содержится описание моста – два числа x и y (0 ≤ x, y < N) – номера соединяемых островов.
Выведите в выходной файл одно число – минимальное количество построенных мостов, по которым можно попасть с любого острова на любой.
4 5 0 1 0 2 1 2 2 3 3 0
4