문제 보기 - 어르신 집배원 (BOI14_postmen)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
500 ms 256 MiB 1270 146 11.5%

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$

제약 조건

시간 제한: 0.5 초

메모리 제한: 256 MB