D. Наибольшая сортировка

Как классная задача D, но выведите лексикографически наибольшую топологическую сортировку или $-1$, если сортировки нет.

Здесь всё честно симметрично: тот же алгоритм Кана, только куча выдаёт не наименьшую доступную вершину, а наибольшую.

Почему жадность работает — рассуждение обменом. На каждом шаге в очередной позиции может стоять любая из доступных сейчас вершин, и никакая другая. Значит, поставив наибольшую доступную, мы делаем эту позицию максимально возможной; а более ранняя позиция при лексикографическом сравнении важнее всех последующих вместе взятых. Проверено перебором: на 60 000 случайных ациклических графов до шести вершин жадный выбор совпал с настоящим максимумом по всем сортировкам.

Технически проще не заводить вторую кучу, а перенумеровать вершины: заменить каждый номер $v$ на $n + 1 - v$, запустить обычный алгоритм с кучей минимумов и вернуть номера обратно.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $m$ ($0 \le m \le 10^5$).

Далее идут $m$ строк с рёбрами. Возможны кратные рёбра и петли.

Либо $n$ чисел в одной строке, либо $-1$.