어르신 집배원 Batch 컴파일 명령

2036년이 되었고 유럽은 고령화 사회에 진입하여 노년층 시민들이 많아졌습니다. 그들을 건강하게 유지하기 위해, 유럽 다수 집단 관리 위원회 (노년층은 다수집단입니다!)는 노년층 시민들이 적은 양의 종이 우편을 배달하는 방안을 발표했습니다. 이 방안은 유럽 전역에 걸쳐서 시행될 것입니다.

부처는 "노인 집배원 시스템"을 아래와 같은 방법으로 창안했습니다: 유럽은 우편 구역으로 분할되었습니다. 한 우편 구역은 도로들과 교차로들의 네트워크를 가지고 있습니다. 이 네트워크의 각 도로는 양방향으로 통행 가능합니다. 각 구역에서 많은 노년층 시민들이 집배원으로서 고용될 수 있습니다. 매일 아침, 각 집배원들은 가방 하나를 받는데, 이 가방 안에는 도로망을 따라 배달해야 할 편지들이 들어 있습니다. 집배원이 이동하는 경로는 반드시 아래 조건을 만족해야 합니다.

• 출발하는 교차로와 도착하는 교차로가 같아야 합니다.
• 같은 교차로를 두 번 이상 지나가면 안 됩니다. (노인들이 당황하면 안 됩니다.)
• 다른 어떤 경로와도 같은 도로를 공유할 수 없습니다. 따라서, 구역의 각 도로는 정확히 한 집배원에게 배정됩니다.

모든 집배원들의 이동 경로는 반드시 도로망 전체를 덮어야 합니다: 다시 말해, 우편 구역의 각 도로는 반드시 정확히 한 집배원의 이동 경로에 존재해야 합니다.

해야 할 일

우편 구역의 도로망이 주어질 때, 집배원들에게 적절한 이동 경로를 배정하여 모든 도로를 적어도 한 명의 집배원이 지나가도록 하는 프로그램을 작성해야 합니다.

입력 형식

입력은 도로망을 나타냅니다.

첫 번째 줄에 두 개의 정수 $N$과 $M$이 주어집니다. $N$은 교차로의 수이고, $M$은 거리의 수입니다. 교차로에는 $1$ 이상 $N$ 이하의 자연수 번호가 붙어 있습니다.

다음 $M$개 줄에는 두 개의 정수 $u$와 $v$ ($1 \le u, v \le N$, $u \neq v$)가 주어집니다. 이것은 $u$번 교차로와 $v$번 교차로를 연결하는 양방향 도로가 있다는 것을 의미합니다.

모든 입력은 아래 조건을 만족합니다.

1. 모든 두 교차로를 연결하는 도로는 최대 1개 존재합니다.
2. 1개 이상의 도로를 따라 이동하여 어떤 교차로에서 다른 모든 교차로로 이동할 수 있습니다.
3. 반드시 적절한 답안이 존재합니다. 다시 말해, 도로망 전체를 덮는 집배원들의 이동 경로가 반드시 존재합니다.

출력 형식

출력의 각 줄은 정확히 한 명의 집배원의 이동 경로를 포함하고 있어야 합니다. 교차로들의 번호는 방문하는 순서대로 차례대로 출력해야 하며, 출발점 (이자 도착점)은 그 줄에서 가장 먼저, 단 한 번 출력되어야 합니다.

여러 개의 답안이 존재한다면, 아무거나 출력해도 좋습니다.

예제

입력

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9

출력

2 3 4 5 8 10 9
7 8 4
1 5 7 6 3

참고

아래의 그림은 도로망과 세 명의 집배원들의 이동 경로를 나타냅니다.

채점

서브태스크 1 (38점)

• $3 \le N \le 2,000$
• $3 \le M \le 100,000$

서브태스크 2 (17점)

• $3 \le N \le 100,000$
• $3 \le M \le 100,000$

서브태스크 3 (45점)

• $3 \le N \le 500,000$
• $3 \le M \le 500,000$