Icy Itinerary

It is a harsh, cold winter in a town of $n$ houses, and everyone is asleep in the early morning. Snow lies deep on the ground except on the $m$ roads that connect some pairs of houses. Only Thomas is awake.

Thomas the mailman has to deliver mail to each of the $n$ houses. The houses are numbered from 1 to $n$. He starts at his own house (house 1) and then visits all the other houses in some order. He can ride a bicycle between two houses connected by a road, and he can use skis between two houses with no road between them. Skis cannot be used on roads, and the bicycle cannot be used off roads. Switching between bicycle and skis is tedious, so he wants to switch at most once.

Find an ordering $a_1, a_2, \cdots, a_n$ of the houses with $a_1 = 1$ such that there is at most one index $i$ ($2 \leq i \leq n-1$) where either

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

In other words, the sequence starts at 1 and switches between road and non-road moves at most once.

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

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i \neq v_i \leq n$), meaning that $u_i$ and $v_i$ are connected by a road. Roads can be used in both directions, and all unordered pairs $\{u_i, v_i\}$ are distinct.

A valid ordering exists for every input.

Print $n$ integers $a_1, a_2, \cdots, a_n$ on one line, the order in which to visit the houses. The first number $a_1$ must be 1.