Задача U. Топологическая сортировка

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков   Ограничение времени:7 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Дан ориентированный ациклический граф. Требуется выполнить топологическую сортировку его вершин. При этом сначала требуется вывести группу вершин, в которые не входит ни одного ребра, затем вершины, в которые входят только рёбра из вершин первой группы, затем те, в тоторые входят только рёбра из вершин первой и второй групп и т.д. В каждой группе номера вершин должны быть отсортированы по возрастанию.

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

Сначала указывается количество вершин V и количество ребер E. Далее перечисляется E пар вершин (vi, vj), задающих ребра. Никакая пара вершин не встречается дважды.

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

Необходимо перечислить V вершин в описанном порядке.

Ограничения

1 <= V <= 1000000, 0 <= E <= 1000000
1 <= vi <= V

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

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

0.062s 0.011s 13