문제
당신은 숲속에서 당신의 간식을 빼앗아간 원숭이를 쫓고 있다.
원숭이가 워낙 기민하게 움직이지만, 당신은 세계에서 가장 좋은 머신건을 이용하여 원숭이를 잡을 수 있다.
원숭이는 잡히지 않기 위해 어떤 나무 뒤에 숨는다.
당신은 이러한 사실을 알고 있고 따라서 특정 나무를 골라서 그곳에 사격을 한다.
당연히 세계에서 가장 좋은 총이기 때문에 나무는 쉽사리 뚫리게 되며, 만약 원숭이가 그 나무 뒤에 숨어 있을 경우 원숭이는 총을 맞아 죽게 된다.
만약 원숭이가 사격한 나무에 없을 경우 원숭이는 사격 소리를 듣고 조용히 이웃의 나무(한 번에 바로 이동할 수 있는 나무)로 이동하게 된다.
워낙 기민한 원숭이기 때문에 당신이 알아채지 못하게 이동을 한다.
원숭이가 한 나무에 계속 숨지 않으며, 반드시 사격 후에 살아있을 경우에는 원숭이는 이웃한 나무로 이동하게 된다.
실탄이 별로 없기 때문에 모든 가능한 경우에 대해 사격 횟수를 최소화하여 원숭이를 잡고자한다.
위의 그림에서 왼쪽 그림의 경우에는 둘 중에 한곳을 계속 사격하게 될 경우에 원숭이를 잡을 수 있다.
만약 원숭이가 처음에 그 나무에 없을 경우에는 다음 사격에서 죽게 된다. 오른쪽의 그림의 경우에는 원숭이를 절대로 잡을 수 없는 경우이다.
입력
입력은 여럿의 테스트 케이스로 이뤄진다. 테스트케이스 사이에는 빈 줄 하나가 입력된다.
테스트 케이스의 첫 번째 줄에는 나무의 개수 N(1≤N≤21)과 이웃한 나무의 쌍 M(0≤M≤210)이 입력된다.
만약 나무의 개수 N과 이웃한 나무의 쌍 M 모두 0 이 입력될 경우 이를 처리하지 않고 프로그램을 종료한다.
나무는 0번부터 N-1번까지 번호가 부여된다.
그 다음 줄부터는 M개의 줄에 0이상 N-1이하의 정수 a와 b가 공백을 사이에 두고 입력된다.
이는 a나무에서 b나무로 혹은 b나무에서 a나무로 바로 이동이 가능함을 뜻한다.
(You may further assume that no tree is adjacent to itself, and there is always a path between any two trees in the forest.)
출력
각 테스트 케이스에 대해 최악의 경우에 원숭이를 잡을 수 없을 경우에는 Impossible을 출력하며,
그렇지 않을 경우 다음과 같은 형식으로 출력한다.
S: T1 T2 ... TS
여기서 S는 모든 경우에도 원숭이를 잡을 수 있게 하기 위한 최소의 사격 수고 Ti는 i번째에 사격해야 하는 나무의 번호를 뜻한다.
사격하는 순서가 여럿 있을 경우 사전 순으로 가장 빠른 것을 출력한다.
예제1
21
01
33
01
12
20
43
01
23
13
00
2:00
Impossible
4:1331