printЗанятие 15

printB. Метро

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В некотором городе есть метро, состоящее из `N` (`1\ ≤\ N\ ≤\ 1000`) станций и `M` (`0\ ≤\ M\ ≤\ 500\ 000`) линий, соединяющих их. Каждая линия обеспечивает проезд между какими-то двумя станциями в обе стороны. Между любой парой станций проведено не более одной линии. Сеть метро построена таким образом, чтобы с каждой станции можно было проехать на каждую (возможно, через промежуточные станции). Назовем это свойство связностью метро.
В связи с изобретением принципиально нового вида транспорта метро стало убыточным, и его работу решили прекратить. На заседании мэрии города было постановлено закрывать каждый год по одной станции, но так, чтобы связность метро каждый раз сохранялась. При закрытии какой-либо станции линии, ведущие от этой станции к другим, естественно, тоже перестают функционировать.
По введенной информации о сети метро разработать какой-либо порядок закрытия станций, при котором метро всегда будет оставаться связным. Например, пусть метро выглядит так, как показано в примере ввода. Тогда станции можно закрывать, например, в порядке 1,2,4,3,5. А порядок 3,1,2,4,5 – не подходит, так как после закрытия 3-й станции метро распадется на четыре не связных части.
Первая строка входного файла будет содержать числа `N` и `M`. В следующих `M` строках находится информация о линиях. Каждая из этих строк содержит через пробел числа `A_i` и `B_i` – две станции, которые соединяет `i`-я линия.
Выходной файл должен состоять из `N` строк. Каждая строка должна содержать одно число – номер станции. Вывести станции нужно в порядке их закрытия.

Пример вывода

5 4
3 1
3 2
3 4
3 5

Пример вывода

1
2
4
3
5
Источник: Белорусская республиканская олимпиада, 2002
loading