EduBrick

M. Порядок выхода

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

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

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

Соседей перебирайте по возрастанию номера. Недостижимые вершины не выводятся.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами.

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

Вершины в порядке выхода, через пробел.

Примеры

ввод
5 4
1 2
1 3
2 4
3 5
вывод
4 2 5 3 1
ввод
6 5
1 2
1 3
1 4
1 5
1 6
вывод
2 3 4 5 6 1
Войдите, чтобы отправлять решения.