Приближается лунный новый год, а Боб решил отправиться на прогулку в ближайший парк.
Парк может быть представлен как связный граф из \(n\) вершин и \(m\) неориентированных ребер. Изначально Боб находился в вершине \(1\) и записал \(1\) в свою записную книжку. Он может переходить из одной вершины в другую по данным ребрам. Каждый раз, когда он посещает вершину, еще не записанную в его книжку, он записывает ее. После того, как он посетит все вершины как минимум по разу, он закончит прогулку, а в его книжке будет записана перестановка вершин \(a_1, a_2, \ldots, a_n\).
Гулять скучно, а решать задачи — интересно. Боб хочет узнать лексикографически минимальную перестановку, которую он может получить по итогам прогулки. Бобу эта задача кажется простой, поэтому он отдал ее вам.
Последовательность \(x\) лексикографически меньше последовательности \(y\), если и только если выполняется один из следующих пунктов:
- \(x\) — префикс \(y\), но \(x \ne y\) (обратите внимание, в этой задаче такое невозможно, так как все рассматриваемые последовательности имеют одинаковую длину);
- в первой позиции, где \(x\) и \(y\) различны, в последовательности \(x\) элемент меньше, чем соответствующий элемент в \(y\).
Выходные данные
Выведите лексикографически наименьшую последовательность \(a_1, a_2, \ldots, a_n\) из тех, которые может записать Боб.
Примечание
В первом примере одним из возможных путей Боба является путь \(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\}\), которая является лексикографически наименьшей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2
1 3
|
1 2 3
|
|
2
|
5 5
1 4
3 4
5 4
3 2
1 5
|
1 4 3 2 5
|
|
3
|
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
|