Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.
Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10
5, 1≤m≤10
5) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).
Выходные данные: Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести −1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 4
1 4
4 3
4 2
3 2 |
1 4 3 2 |