e-olymp
Məsələlər

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

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

Компонентой реберной двусвязности графа (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-я вершина.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
6 7
1 2
2 3
3 1
1 4
4 5
4 6
5 6
Çıxış verilənləri
2
1 1 1 2 2 2
Mənbə ЛКШ-2011 Севастополь 08.08.2011 д.1 1-я лига
Пропавшая цивилизация