뛰어다니는 원숭이

당신은 숲에서 원숭이를 쫓는 사냥꾼이며, 무엇이든 관통하는 전자동 소총으로 원숭이를 잡으려 한다. 원숭이는 어느 한 나무의 가지 뒤에 숨어 있어 보이지 않는다. 당신은 나무 하나를 겨냥해 쏠 수 있고, 총알은 가지를 관통하므로 그 나무에 원숭이가 있으면 즉시 잡는다. 없으면, 당신이 재장전하는 사이에 원숭이는 당신 몰래 이웃한 나무로 뛰어 옮겨 간다. 원숭이는 총을 쏜 뒤에는 결코 같은 자리에 머무르지 않는다. 원숭이의 처음 위치와 이후의 이동이 어떻든 반드시 원숭이를 잡을 수 있는 전략이 있는지 알아내고, 있다면 그것을 보장하는 가장 짧은 발사 순서를 구하려 한다.

예를 들어, 이웃한 나무가 두 그루뿐인 숲을 생각하자. 같은 나무를 두 번 쏘면 반드시 원숭이를 잡을 수 있다. 첫 번째 발사는 원숭이가 애초에 그 나무에 있었다면 성공한다. 그렇지 않았다면 원숭이는 다른 나무에 있었고, 두 번째로 쏠 때는 반드시 당신이 쏘는 나무로 옮겨 와 있다.

하지만 숲의 모양에 따라서는 승리를 보장할 수 없을 수도 있다. 한 예로 세 그루의 나무가 서로 모두 연결되어 있는 경우가 있다. 어디를 겨냥하든 어느 순간에나 원숭이가 있을 수 있는 위치가 항상 두 곳 존재한다. (여기서는 원숭이가 당신이 다음에 겨냥할 나무를 계속 알아맞힐 수도 있는 최악의 경우를 고려한다.)

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 하나의 빈 줄로 구분된다. 각 테스트 케이스는 두 정수 $n$과 $m$이 있는 줄로 시작한다 ($1 \le n \le 21$). $n$은 숲에 있는 나무의 수이고, $m$은 나무 사이의 인접 관계의 수이다. 이어지는 $m$개의 줄에는 각각 $0$ 이상 $n-1$ 이하의 서로 다른 두 정수가 주어지며, 이는 인접한 나무 쌍의 번호이다. 쌍 안에서 두 나무의 순서는 의미가 없고, 같은 쌍이 두 번 나오지 않는다. 어떤 나무도 자기 자신과 인접하지 않으며, 숲의 임의의 두 나무 사이에는 항상 경로가 존재한다.

입력은 0이 두 개만 있는 줄로 끝나며, 이 줄 앞에도 빈 줄이 온다.

각 테스트 케이스마다 한 줄을 출력한다. 작업이 불가능하면 그 줄에는 단어 Impossible 하나만 출력한다. 가능하면, 조건을 만족하는 가장 짧은 발사 순서를 출력한다. 먼저 순서의 길이 $L$을 쓰고, 콜론과 공백에 이어, 쏠 나무의 번호들을 순서대로 하나의 공백으로 구분해 출력한다(즉, 줄은 L: V_1 V_2 ... V_L 형태이다). 가장 짧은 순서가 여러 개이면 사전순으로 가장 작은 것을 출력한다. (두 순서를 비교할 때, 처음으로 다른 위치에서 값이 더 작은 쪽이 사전순으로 더 작다.)