e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Strong Connected Components

Конденсація графа

Вам задано зв'язний орієнтовний граф з n вершинами та m ребрами. Знайдіть компоненти сильної зв'язності заданого графа та топологічно відсортуйте його конденсацію.

Вхідні дані

Граф задано наступним чином: перший рядок містить числа n та m (1n20000, 1m200000). Кожен з наступних m рядків містить описи ребер - два цілих числа з діапазону від 1 до n - номери початку та кінця ребра.

Вихідні дані

У першому рядку виведіть кількість компонент сильної зв'язності у заданому графі. У наступному рядку виведіть n чисел - для кожної вершини виведіть номер компоненти сильної зв'язності, якій належить ця вершина. Компоненти сильної зв'язності повинні бути пронумеровані таким чином, щоб для довільного ребра номер компоненти сильної зв'язності його початку не перевищував номер компоненти сильної зв'язностї його кінця.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4
Вихідні дані #1
2
1 1 1 2 2 2