eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #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