Мосты
Мосты
Владения короля Джулиана расположены на n островах, пронумерованных от 1 до n. Некоторые пары островов соединены друг с другом мостами, по которым можно перемещаться в две стороны. Всего между островами есть m мостов. От любого острова можно добраться до любого другого, перемещаясь по мостам.
Будем называть мост критическим, если в случае обрушения этого моста будут существовать такие две острова, что от одного из них нельзя добраться до другого, перемещаясь по оставшимся мостам.
Король Джулиан очень беспокоится о безопасности и доступности сообщения в своих владениях. Он хочет построить дополнительные мосты между некоторыми парами островов так, чтобы между островами не осталось критических мостов. Так как король в то же время еще и экономный, он хочет выяснить, какое минимальное количество дополнительных мостов можно построить, чтобы выполнить данное требование.
Входные данные
В первой строке даны два целых числа n и m - количество островов и количество мостов между ними (2 ≤ n ≤ 105
, 1 ≤ m ≤ 2 * 105
).
В следующих m строках дано по два целых числа ai
и bi
(1 ≤ ai
, bi
≤ n, ai
≠ bi
) - номера островов, соединенных i-м мостом.
Гарантируется, что от любого острова можно добраться до любого другого, перемещаясь по мостам.
Выходные данные
Выведите одно целое число - минимальное количество дополнительных мостов, которое нужно построить, чтобы между островами не было критических мостов.
5 5 1 2 2 3 2 4 2 5 4 5
1
2 1 1 2
1