EduBrick

J. Компоненты рёберной двусвязности

3000 мс · 256 МБ · всё или ничего

Уберите из графа все мосты и посчитайте, на сколько компонент связности он распадётся. Эти компоненты называют компонентами рёберной двусвязности: внутри каждой из них любые две вершины соединены хотя бы двумя рёберно непересекающимися путями.

Считается в два прохода: сначала обычным поиском мостов, потом обходом по всем рёбрам, кроме них.

Полезно понимать, что получается: если стянуть каждую такую компоненту в вершину, останется лес мостов — циклов в нём быть не может. Именно на этом стоит теорема Роббинса из классной задачи K: ориентация существует ровно тогда, когда этот лес состоит из одной вершины.

Формат ввода

Первая строка содержит числа nn (1≤n≤2⋅1041 \le n \le 2 \cdot 10^4) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами. Граф не обязан быть связным; возможны кратные рёбра и петли.

Формат вывода

Одно число.

Примеры

ввод
6 7
1 2
2 3
3 4
1 3
4 5
4 6
5 6
вывод
2
ввод
2 2
1 2
1 2
вывод
1
Войдите, чтобы отправлять решения.