Skip to content

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