e-olymp
Competitions

ADA University - January 14 -Strong connected components

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

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

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

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

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

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

Time limit 1 seconds
Memory limit 64 MiB
Input example #1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4
Output example #1
2
1 1 1 2 2 2