해밀토니안 하이킹

Alice는 하이킹을 좋아한다. 그녀는 배낭 하나만 메고 여러 날 동안 숲과 산을 넘으며 여행하곤 한다. 내년 여름, 그녀는 산장이 많은 아름다운 지역으로 여행을 가기로 했다. 산장은 하이커가 침낭을 펼치고 하룻밤 묵을 수 있는 곳이다. 산장들은 하이킹 코스로 연결되어 있으며, 이 코스는 그 지역의 경치를 따라 다음 산장으로 이어진다.

Alice의 계획은 여러 날에 걸친 하이킹이다. 그녀는 매일 코스를 따라 걸어 새로운 산장에서 하룻밤을 보낸다. 하루에 최대 세 개의 코스까지 걸을 수 있다. 네 개의 코스를 걸으면 너무 지치기 때문이다. 최대한 많은 산장을 경험하기 위해, Alice는 모든 산장에서 적어도 한 번은 자겠다고 결심했다. 그러나 여름의 날 수는 한정되어 있다. 그녀는 같은 산장을 여러 번 방문할 시간이 없다.

Alice는 이를 위해서는 하이킹 계획을 신중하게 세워야 한다는 것을 깨달았고, 그러한 경로를 어떻게 찾을지 궁금해한다. 매일 Alice가 어느 산장으로 걸어가야 하는지 결정하라. 그림 H.1은 두 번째 예제에 대한 가능한 경로를 보여준다.

그림 H.1: 두 번째 예제의 입력과 가능한 경로(빨간 점선 화살표).

입력은 다음과 같이 주어진다.

• 두 정수 $n$ ($2\leq n\leq 2\cdot 10^5$)과 $m$ ($1\leq m\leq 2\cdot 10^5$)이 있는 한 줄. $n$은 산장의 수, $m$은 하이킹 코스의 수이다.
• $m$개의 줄에 각각 두 정수 $x,y$ ($1\leq x,y\leq n$, $x\neq y$)가 주어지며, 이는 산장 $x$와 $y$ 사이에 하이킹 코스가 있음을 나타낸다.

모든 산장은 다른 모든 산장에서 도달할 수 있다. 두 산장 사이에는 하이킹 코스가 최대 하나만 존재한다.

Alice가 $n$개의 산장을 방문해야 하는 순서를 출력하라.

전체 하이킹 코스의 수를 최소화할 필요는 없다.

유효한 해가 여러 개라면, 그중 아무거나 출력해도 된다.