Вам задан связный ориентированный граф. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1 ≤ N ≤ 20 000, 1 ≤ M ≤ 200 000) – число вершин и ребер соответственно. Каждая из следующих M строк содержит описание ребра: два целых числа из диапазона от 1 до N – номера начала и конца ребра.
В первой строке выходного файла OUTPUT.TXT выведите число K – количество компонент сильной связности в заданном графе. На следующей строке выведите N чисел – для каждой вершины от 1 до N выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.
№ | INPUT.TXT | OUTPUT.TXT |
1 | 10 19
1 4
7 8
5 10
8 9
9 6
2 6
6 2
3 8
9 2
7 2
9 7
4 5
3 6
7 3
6 7
10 8
10 1
2 9
2 7 | 2 1 2 2 1 1 2 2 2 2 1 |