Bridges. Мосты
Шешімді жөнелту
Ұпайлар:
1
Уақыт шектеуі:
2.0s
Жад шектеуі:
64M
Author:
Problem types
Рұқсат етілген тілдер
Assembly, Awk, Brain****, C, C++, Java, Pascal, Perl, Python, Sed, Text
Дан неориентированный граф. Требуется найти все мосты в нем.
Входные данные
Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) — количества вершин и ребер графа соответственно (\(n \leqslant 20\,000\), \(m \leqslant 200\,000\)).
Следующие \(m\) строк содержат описание ребер по одному на строке. Ребро номер \(i\) описывается двумя натуральными числами \(b_i\), \(e_i\) — номерами концов ребра (\(1 \leqslant b_i, e_i \leqslant n\)).
Выходные данные
Первая строка выходного файла должна содержать одно натуральное число \(b\) — количество мостов в заданном графе. На следующей строке выведите \(b\) целых чисел — номера ребер, которые являются мостами, в возрастающем порядке. Ребра нумеруются с единицы в том порядке, в котором они заданы во входном файле.
Примеры
Ввод 1
10 16
5 7
2 8
6 1
6 4
1 2
2 10
4 8
3 9
10 8
9 5
10 4
6 8
1 4
3 7
10 3
6 2
Ответ 1
1
15