Компоненты реберной двусвязности
Компонентой реберной двусвязности графа (V, E) называется подмножество вершин S S V , такое что для любых различных u и v из этого множества существует не менее двух реберно не пересекающихся путей из u в v.
Дан неориентированный граф. Требуется выделить компоненты реберной двусвязности в нем.
Входные данные
Первая строка входного файла содержит два натуральных числа n и m — количества вершин и ребер графа соответственно (n ≤ 20000, m ≤ 200000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается двумя натуральными числами b_i, e_i — номерами концов ребра (1 ≤ b_i, e_i ≤ n).
Выходные данные
В первой строке выходного файла выведите целое число k — количество компонент реберной двусвязности графа. Во второй строке выведите n натуральных чисел a_1, a_2, ..., a_n, не превосходящих k, где a_i — номер компоненты реберной двусвязности, которой принадлежит i-я вершина.