Processing math: 100%

Задача D. Конденсация графа

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

Формат входного файла

Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до N - номера начала и конца ребра.

Формат выходного файла

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

Ограничения

1N20000, 1M2000000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4
2
1 1 1 2 2 2

0.045s 0.008s 13