I. Минимизация мостов
3000 мс · 256 МБ · всё или ничего
Добавьте в граф ровно одно ребро так, чтобы количество мостов стало наименьшим возможным. Выведите это количество.
Граф может быть несвязным, содержать петли и кратные рёбра. Добавляемое ребро тоже может быть петлёй или дублировать существующее.
Формат ввода
В первой строке и (, ). В каждой из следующих строк — концы ребра. Возможны петли и кратные рёбра, граф может быть несвязным.
Формат вывода
Выведите наименьшее число мостов, которого можно добиться добавлением ровно одного ребра.
Примеры
ввод
6 7 1 2 2 3 3 4 1 3 4 5 4 6 5 6
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.