EduBrick

I. Минимизация мостов

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

Добавьте в граф ровно одно ребро так, чтобы количество мостов стало наименьшим возможным. Выведите это количество.

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

Формат ввода

В первой строке nn и mm (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5, 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5). В каждой из следующих mm строк — концы ребра. Возможны петли и кратные рёбра, граф может быть несвязным.

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

Выведите наименьшее число мостов, которого можно добиться добавлением ровно одного ребра.

Примеры

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