페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2387

원숭이 사냥 1s 128MB

문제

당신은 숲속에서 당신의 간식을 빼앗아간 원숭이 로봇을 쫓고 있다. 

원숭이 로봇은 워낙 기민하게 움직이지만, 당신은 세계에서 가장 좋은 머신건을 이용하여 원숭이 로봇을 잡을 수 있다.

 

원숭이 로봇은 잡히지 않기 위해 어떤 나무 뒤에 숨는다. 

당신은 이러한 사실을 알고 있고 따라서 특정 나무를 골라서 그곳에 사격을 한다. 

당연히 세계에서 가장 좋은 총이기 때문에 나무는 쉽사리 뚫리게 되며, 만약 원숭이 로봇이 그 나무 뒤에 숨어 있을 경우 원숭이 로봇은 총을 맞아 작동이 멈추게 된다. 

만약 원숭이 로봇이 사격한 나무에 없을 경우 원숭이 로봇은 사격 소리를 듣고 조용히 이웃의 나무(한 번에 바로 이동할 수 있는 나무)로 이동하게 된다. 

워낙 기민한 원숭이 로봇이기 때문에 당신이 알아채지 못하게 이동을 한다. 

원숭이 로봇이 한 나무에 계속 숨지 않으며, 반드시 사격 후에 살아있을 경우에는 원숭이 로봇은 이웃한 나무로 이동하게 된다.

 

실탄이 별로 없기 때문에 모든 가능한 경우에 대해 사격 횟수를 최소화하여 원숭이 로봇을 잡고자한다.

위의 그림에서 왼쪽 그림의 경우에는 둘 중에 한곳을 계속 사격하게 될 경우에 원숭이 로봇을 잡을 수 있다. 

만약 원숭이 로봇이 처음에 그 나무에 없을 경우에는 다음 사격에서 작동이 멈추게 된다. 오른쪽의 그림의 경우에는 원숭이 로봇을 절대로 잡을 수 없는 경우이다.


입력

입력은 여럿의 테스트 케이스(최대 15개)로 이뤄진다. 테스트케이스 사이에는 빈 줄 하나가 입력된다. 

테스트 케이스의 첫 번째 줄에는 나무의 개수 N (1≤N≤21)과 이웃한 나무의 쌍 M (0≤M≤210)이 입력된다. 

만약 나무의 개수 N과 이웃한 나무의 쌍 M 모두 0 이 입력될 경우 이를 처리하지 않고 프로그램을 종료한다. 

나무는 0번부터 N-1번까지 번호가 부여된다. 

그 다음 줄부터는 M개의 줄에 0이상 N-1이하의 정수 a와 b (a \neq b )가 공백을 사이에 두고 입력된다. 이는 a번 나무에서 b번 나무로, 혹은 b번 나무에서 a번 나무로 바로 이동이 가능함을 뜻한다. 이때, 임의의 나무에서 임의의 다른 나무까지 가는 방법이 항상 존재한다.


출력

각 테스트 케이스에 대해 최악의 경우에 원숭이 로봇을 잡을 수 없을 경우에는 Impossible을 출력하며, 

그렇지 않을 경우 다음과 같은 형식으로 출력한다.

S\ :\ T_1 \ T_2 \ ... \ T_S 

여기서 S는 모든 경우에도 원숭이 로봇을 잡을 수 있게 하기 위한 최소의 사격 수고 T_i는 i번째에 사격해야 하는 나무의 번호를 뜻한다. 

사격하는 순서가 여럿 있을 경우 사전 순으로 가장 빠른 것을 출력한다.


예제 

2 1

0 1



3 3

0 1

1 2

2 0



4 3

0 1

2 3

1 3



0 0
2: 0 0

Impossible

4: 1 3 3 1


출처

SWERC 2010 Jumping Monkey

로그인해야 코드를 작성할 수 있어요.