問題
농부 창호는 목장의 모든 길을 다니며 잡초를 뽑고자 한다.
잡초는 현재 모든 길에 존재한다. 번호가 매겨진 두개의 장소를 잇는 것을 길이라고 한다.
창호는 너무 게으르기 때문에 모든 길을 정확히 한번만 거쳐서 잡초를 뽑고자 한다.
잡초를 뽑기 전의 시작 위치나 끝날 때의 도착 위치는 어느 장소에서 행하든 상관이 없다고 가정하자.
또한 목장의 구조가 잘 설계 되어 있기 때문에 어느 특정장소에서든 다른 장소로 이동할 수 있는 경로가 존재한다.
목장의 길들의 정보가 주어졌을 때
창호가 모든 길을 한번만 거쳐서 잡초를 뽑고자 할 때의 경로를 출력하는 프로그램을 작성하라.
輸入
입력의 첫 번째 줄에는 목장의 길의 개수 N(N≤1,024)이 주어진다. 그 다음 줄부터 N개의 줄에는 두개의 숫자 i, j (1≤i, j≤500) 장소i와 장소j 사이를 잇는 길이 존재한다는 것이다.
輸出
창호가 거치게 되는 장소의 번호를 한 줄에 하나씩 출력한다. 불가능한 경우는 입력되지 않으며 사전 순으로 가장 빠른 경로를 출력한다.
範例
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
1
2
3
4
2
5
4
6
5
7
需要登入才能撰寫程式碼。