Задачи
Компоненты реберной двусвязности
Компоненты реберной двусвязности
\includegraphics{https://static.e-olymp.com/content/cc/cc8a15c4c87b4c7e92efe076a394dd47b084fd99.jpg}
Компонентой реберной двусвязности графа (\textbf{V}, \textbf{E}) называется подмножество вершин \textbf{S} \textbf{S} \textbf{V} , такое что для любых различных \textbf{u} и \textbf{v} из этого множества существует не менее двух реберно не пересекающихся путей из \textbf{u} в \textbf{v}.
Дан неориентированный граф. Требуется выделить компоненты реберной двусвязности в нем.
\InputFile
Первая строка входного файла содержит два натуральных числа \textbf{n} и \textbf{m} --- количества вершин и ребер графа соответственно (\textbf{n} ≤ \textbf{20000}, \textbf{m} ≤ \textbf{200000}). Следующие \textbf{m} строк содержат описание ребер по одному на строке. Ребро номер \textbf{i} описывается двумя натуральными числами \textbf{b_i}, \textbf{e_i} --- номерами концов ребра (\textbf{1} ≤ \textbf{b_i}, \textbf{e_i} ≤ \textbf{n}).
\OutputFile
В первой строке выходного файла выведите целое число \textbf{k} --- количество компонент реберной двусвязности графа. Во второй строке выведите \textbf{n} натуральных чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n}, не превосходящих \textbf{k}, где \textbf{a_i} --- номер компоненты реберной двусвязности, которой принадлежит \textbf{i}-я вершина.
Входные данные #1
6 7 1 2 2 3 3 1 1 4 4 5 4 6 5 6
Выходные данные #1
2 1 1 1 2 2 2