Задан ориентированный ацикличный граф из n вершин и m ребер. В нем нет петель и кратных ребер. Граф может быть несвязным.
Необходимо так расставить метки на вершинах, чтобы:
- Метки образовывали корректную перестановку длины n. Это последовательность целых чисел, такая, что каждое число от 1 до n встречается в ней ровно один раз.
- Если существует ребро от вершины v к вершине u, то labelv должно быть меньше labelu.
- Перестановка должна быть лексикографически наименьшей среди всех подходящих.
Найдите последовательность, подходящую под все условия.
Выходные данные
Выведите n чисел — лексикографически наименьшую корректную перестановку меток вершин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2
1 3
3 2
|
1 3 2
|
|
2
|
4 5
3 1
4 1
2 3
3 4
2 4
|
4 1 2 3
|
|
3
|
5 4
3 1
2 1
2 3
4 5
|
3 1 2 4 5
|