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