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

Дан ориентированный граф. Необходимо построить топологическую сортировку.

Напомним:

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

В первой строке входного файла два натуральных числа $N$ и $M$ $(1 \leq N, M \leq 100\,000)$ — количество вершин и рёбер в графе соответственно. Далее в $M$ строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выведите любую топологическую сортировку графа в виде последовательности номеров вершин (перестановка чисел от 1 до N). Если топологическую сортировку графа построить невозможно, выведите -1.

Если отбросить формализм, то можно сказать, что нужно сделать следующее:

1. Перенумеровать все вершины нашего графа.

2. Для всех M рёбер из входных данных и только для них должно выполняться условие, что ребро ведёт из вершины с меньшим номером в вершину с большим номером.

Давайте посмотрим на ответ к примеру:

4 6 3 1 2 5

Это значит, что вершина, которая в исходной нумерации была 4 становится 1, 6 становится 2, 3 остаётся 3, 1 становится 4, 2 становится 5, а 5 становится 6. Давайте теперь составим таблицу соответствия номеров вершин в исходной нумерации и номеров вершин в новой нумерации.

1 2 3 4 5 6 (номера вершин в исходной нумерации)

4 5 3 1 6 2 (номера вершин в новой нумерации)

Посмотрим на рёбра:

1 2 -> 4 5

3 2 -> 3 5

4 2 -> 1 5

2 5 -> 5 6

6 5 -> 2 6

4 6 -> 1 2

В старой нумерации нарушался критерий топологической сортировки, однако в новой он выполняется.