Learning path · Algorithm Foundations
← Back to lesson · Graphs and trees미술관의 모든 전시실을 한 번씩 관람하기
Unrated
한국어
Language
Contribute a translation- Time limit
- 1000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
미술관의 전시실 연결 관계가 그래프로 주어진다. 한 번 방문한 전시실을 다시 방문하지 않으면서 모든 전시실을 관람하는 경로를 출력하시오. 그러한 경로가 여러 개이면 방문 순서를 앞에서부터 비교하여 번호가 작은 쪽을 출력한다.
Input
첫째 줄에 전시실의 수 $n$과 통로의 수 $m$이 공백을 사이에 두고 주어진다. ($1 \le n \le 10$) 다음 $m$개의 줄에 통로가 잇는 두 전시실의 번호가 한 줄에 하나씩 주어진다. 전시실 번호는 0부터 $n-1$까지이고, 통로는 방향이 없다.
Output
모든 전시실을 한 번씩 지나는 경로를 전시실 번호를 `-`로 이어 한 줄에 출력한다. 그러한 경로가 없으면 Impossible을 출력한다.
Examples
Sample input 1
7 11 0 1 0 2 0 3 0 6 1 2 2 6 3 4 3 5 3 6 4 5 5 6
Sample output 1
0-1-2-6-3-4-5
Sample input 2
4 2 0 1 2 3
Sample output 2
Impossible
Tags
No tags yet