e-olymp
Задачі

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

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

Компонентой реберной двусвязности графа (V, E) называется подмножество вершин SSTM_podmnV , такое что для любых различных u и v из этого множества существует не менее двух реберно не пересекающихся путей из u в v.

Дан неориентированный граф. Требуется выделить компоненты реберной двусвязности в нем.

Входные данные

Первая строка входного файла содержит два натуральных числа n и m — количества вершин и ребер графа соответственно (n20000, m200000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1bi, ein).

Выходные данные

В первой строке выходного файла выведите целое число k — количество компонент реберной двусвязности графа. Во второй строке выведите n натуральных чисел a1, a2, ..., an, не превосходящих k, где ai — номер компоненты реберной двусвязности, которой принадлежит i-я вершина.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #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
Джерело ЛКШ-2011 Севастополь 08.08.2011 д.1 1-я лига
Пропавшая цивилизация