어르신 집배원 Batch 컴파일 명령
시간 제한 | 메모리 제한 | 제출 횟수 | 통과한 사람 수 | 비율 |
---|---|---|---|---|
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개 이상의 도로를 따라 이동하여 어떤 교차로에서 다른 모든 교차로로 이동할 수 있습니다.
- 반드시 적절한 답안이 존재합니다. 다시 말해, 도로망 전체를 덮는 집배원들의 이동 경로가 반드시 존재합니다.
출력 형식
출력의 각 줄은 정확히 한 명의 집배원의 이동 경로를 포함하고 있어야 합니다. 교차로들의 번호는 방문하는 순서대로 차례대로 출력해야 하며, 출발점 (이자 도착점)은 그 줄에서 가장 먼저, 단 한 번 출력되어야 합니다.
여러 개의 답안이 존재한다면, 아무거나 출력해도 좋습니다.
예제
입력 | 출력 |
---|---|
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