EduBrick

I. Мосты

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

Мост — ребро, при удалении которого число компонент связности растёт. Найдите все мосты неориентированного графа.

Обход в глубину делит рёбра на два вида: древесные — по которым он впервые заходил в вершину, и обратные — ведущие в уже посещённую. Мостом может быть только древесное ребро: обратное лежит на цикле вместе с частью дерева.

Для каждой вершины считается функция подъёма low[v]low[v] — наименьшее tintin, до которого можно добраться из поддерева vv, спустившись по древесным рёбрам и поднявшись не более чем по одному обратному:

low[v]=min⁡(tin[v], min⁡обратное v→utin[u], min⁡сын clow[c]).low[v] = \min(tin[v],\ \min_{\text{обратное } v \to u} tin[u],\ \min_{\text{сын } c} low[c]).

Древесное ребро (p,v)(p, v) — мост тогда и только тогда, когда low[v]>tin[p]low[v] > tin[p]: из поддерева vv нельзя обойти это ребро.

Единственная тонкость — кратные рёбра. Возврат запрещается по тому же ребру, а не в ту же вершину: иначе второе ребро между теми же вершинами будет пропущено, и оба они ошибочно окажутся мостами. Поэтому в списке смежности хранится номер ребра.

Формат ввода

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

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

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

В первой строке — количество мостов bb.

Во второй — bb номеров рёбер по возрастанию. Рёбра нумеруются с единицы в порядке ввода. Если мостов нет, вторая строка пустая.

Примеры

ввод
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

Войдите, чтобы отправлять решения.