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