EduBrick

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

1000 мс · 256 МБ · всё или ничего

Дан ориентированный граф. Выпишите вершины в таком порядке, чтобы каждое ребро вело слева направо. Если это невозможно, сообщите об этом.

Порядков обычно много, поэтому в ответе нужен лексикографически наименьший - тот, который начинается с наименьшей возможной вершины, при равном начале продолжается наименьшей возможной, и так далее.

Формат ввода

В первой строке - числа nn и mm (1≤n≤1051 \le n \le 10^5, 0≤m≤1050 \le m \le 10^5): количество вершин и рёбер.

В следующих mm строках - пары uu, vv: ребро из uu в vv. Возможны кратные рёбра и петли.

Формат вывода

Выведите лексикографически наименьший топологический порядок - nn чисел. Если порядка не существует, выведите -1.

Примеры

ввод
6 6
1 2
3 2
4 2
2 5
6 5
4 6
вывод
1 3 4 2 6 5
ввод
3 3
1 2
2 3
3 1
вывод
-1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.