Icy Itinerary

문제

It is a harsh and cold winter, in a town consisting of $nn$ houses. Everybody is asleep in the early morning hours. The snow lies deep on the ground, except on the $mm$ roads that connect some pairs of houses. Only Thomas is awake.

Thomas the mailman needs to deliver mail to each of the $nn$ houses in the town. The houses are numbered from $11$ to $nn$. Thomas will start in his own house (house $11$), and then visit all the other houses in some order. He can use a bicycle to get between two houses connected by a road, and he can use skis if there is no road between the houses. But it is not possible to use skis on roads and the bicycle outside of roads. Switching between bicycle and skis is tedious, so Thomas would like to do this at most once.

Your task is to find an ordering $a_1,a_2,\cdots ,a_{n}a\_1,\; a\_2,\; \backslash cdots,\; a\_n$ of the $nn$ houses so that $a_1=1a\_1\; =\; 1$, and there is at most one index $ii$ ($2\le i\le n-12\; \backslash leq\; i\; \backslash leq\; n-1$) such that either

1. $a_{i-1}a\_\{i-1\}$ and $a_{i}a\_i$ are connected by a road, but $a_{i}a\_i$ and $a_{i+1}a\_\{i+1\}$ are not, or
2. $a_{i-1}a\_\{i-1\}$ and $a_{i}a\_i$ are not connected by a road, but $a_{i}a\_i$ and $a_{i+1}a\_\{i+1\}$ are.

In other words, the sequence starts at $11$ and switches between using roads and non-roads at most once.

입력

The first line contains two integers $nn$, $mm$ ($2\le n\le 3\cdot {10}^{5}2\; \backslash leq\; n\; \backslash leq\; 3\; \backslash cdot\; 10^5$, $0\le m\le 3\cdot {10}^{5}0\; \backslash leq\; m\; \backslash leq\; 3\; \backslash cdot\; 10^5$), the number of houses and the number of roads.

The next $mm$ lines each contain two integers $u_i,v_{i}u\_i,\; v\_i$ ($1\le u_i\mathrm{\ne }{v}_i\le n1\; \backslash leq\; u\_i\; \backslash neq\; v\_i\; \backslash leq\; n$), meaning that $u_{i}u\_i$ and $v_{i}v\_i$ are connected by a road. The roads can be used in both directions, and all the unordered pairs $\{u_i,v_i\}\backslash \{u\_i,\; v\_i\backslash \}$ are distinct.

There exists a valid ordering for every case in the input.

출력

Print $nn$ integers $a_1,a_2,\cdots ,a_{n}a\_1,\; a\_2,\; \backslash cdots,\; a\_n$ on one line, the order in which to visit the houses.

Remember that the first number $a_{1}a\_1$ should be $11$.