D. Лунный новый год и прогулка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Приближается лунный новый год, а Боб решил отправиться на прогулку в ближайший парк.

Парк может быть представлен как связный граф из $$$n$$$ вершин и $$$m$$$ неориентированных ребер. Изначально Боб находился в вершине $$$1$$$ и записал $$$1$$$ в свою записную книжку. Он может переходить из одной вершины в другую по данным ребрам. Каждый раз, когда он посещает вершину, еще не записанную в его книжку, он записывает ее. После того, как он посетит все вершины как минимум по разу, он закончит прогулку, а в его книжке будет записана перестановка вершин $$$a_1, a_2, \ldots, a_n$$$.

Гулять скучно, а решать задачи — интересно. Боб хочет узнать лексикографически минимальную перестановку, которую он может получить по итогам прогулки. Бобу эта задача кажется простой, поэтому он отдал ее вам.

Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если и только если выполняется один из следующих пунктов:

  • $$$x$$$ — префикс $$$y$$$, но $$$x \ne y$$$ (обратите внимание, в этой задаче такое невозможно, так как все рассматриваемые последовательности имеют одинаковую длину);
  • в первой позиции, где $$$x$$$ и $$$y$$$ различны, в последовательности $$$x$$$ элемент меньше, чем соответствующий элемент в $$$y$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — числе вершин и ребер в графе, соответственно.

Следующие $$$m$$$ строк описывают неориентированные ребра графа. $$$i$$$-я из этих строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — вершины, соединенные $$$i$$$-м ребром.

Обратите внимание, что в графе могут быть кратные ребра и петли. Гарантируется, что граф связный.

Выходные данные

Выведите лексикографически наименьшую последовательность $$$a_1, a_2, \ldots, a_n$$$ из тех, которые может записать Боб.

Примеры
Входные данные
3 2
1 2
1 3
Выходные данные
1 2 3
Входные данные
5 5
1 4
3 4
5 4
3 2
1 5
Выходные данные
1 4 3 2 5
Входные данные
10 10
1 4
6 8
2 5
3 7
9 4
5 6
3 4
8 10
8 9
1 10
Выходные данные
1 4 3 7 9 8 6 5 2 10
Примечание

В первом примере одним из возможных путей Боба является путь $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$. Боб в этом случае запишет последовательность $$$\{1, 2, 3\}$$$, которая является лексикографически наименьшей.

Во втором примере Боб может пойти по пути $$$1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 5$$$. Тогда он запишет последовательность $$$\{1, 4, 3, 2, 5\}$$$, которая является лексикографически наименьшей.