Компоненты реберной двусвязности

Компонентой реберной двусвязности графа (V, E) называется подмножество вершин SSV , такое что для любых различных 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₁, a₂, ..., a_n, не превосходящих k, где a_i — номер компоненты реберной двусвязности, которой принадлежит i-я вершина.