시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 22 6 5 31.250%

문제

상근이네 반에는 총 K명의 학생이 있다. 그 중 일부는 서로를 엄청나게 싫어한다. 서로 싫어하는 친구는 교실 밖에서 절대 마주치지 않는 경로를 이용해 교실로 이동하려고 한다. 이런 경로를 찾아보자.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 찾아야하는 경로의 수 K와 교차로의 수 N이 주어진다. 교차로는 1번부터 N번까지 번호가 매겨져 있다. 다음 N개 줄에는 각 교차로가 어떤 교차로와 연결되어 있는지 주어지며, 교차로 번호가 증가하는 순서로 주어진다. 모든 교차로는 적어도 한 교차로와 연결되어 있다.

입력의 마지막 줄에는 0 0이 주어진다.

1 ≤ K ≤ 100, 2 ≤ N ≤ 5000이며 모든 학생은 1번 교차로에서 시작하고, 교실은 2번 교차로에 있다.

출력

각 테스트 케이스마다 "Case #:" 형식으로 케이스 번호를 출력한다. 그 다음, K개의 겹치지 않는 경로 (1번에서 출발해 2번으로 도착하는 경로)가 존재하면 K개 줄에 각 경로를 출력한다. 없는 경우에는 "Impossible"을 출력한다.

각 테스트 케이스의 정답을 출력한 다음에는 빈 줄을 하나 출력한다.

예제 입력

3 5
3 4 5
3 4 5
1 2
1 2
1 2
4 5
3 4 5
3 4 5
1 2
1 2
1 2
0 0

예제 출력

Case 1:
1 3 2
1 4 2
1 5 2

Case 2:
Impossible

힌트