시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 340 78 31 17.614%

문제

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

입력

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

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

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

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

Case 2:
Impossible

힌트

W3sicHJvYmxlbV9pZCI6Ijc2MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNTBcdWMyZTRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWUzOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YmMxOFx1YzVkMFx1YjI5NCBcdWNkMWQgS1x1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkZjggXHVjOTExIFx1Yzc3Y1x1YmQ4MFx1YjI5NCBcdWMxMWNcdWI4NWNcdWI5N2MgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjMTFjXHViODVjIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWNlNWNcdWFkNmNcdWIyOTQgXHVhZDUwXHVjMmU0IFx1YmMxNlx1YzVkMFx1YzExYyBcdWM4MDhcdWIzMDAgXHViOWM4XHVjOGZjXHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YWQ1MFx1YzJlNFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVhY2JkXHViODVjXHViOTdjIFx1Y2MzZVx1YzU0NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjM2VcdWM1NDRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOCBLXHVjNjQwIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVhZDUwXHVjYzI4XHViODVjXHVhYzAwIFx1YzViNFx1YjVhNCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM2NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWQ1MFx1Y2MyOFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFkNTBcdWNjMjhcdWI4NWNcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWFkNTBcdWNjMjhcdWI4NWNcdWM2NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MSAmbGU7IEsgJmxlOyAxMDAsIDIgJmxlOyBOICZsZTsgNTAwMFx1Yzc3NFx1YmE3MCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzQwIDFcdWJjODggXHVhZDUwXHVjYzI4XHViODVjXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCwgXHVhZDUwXHVjMmU0XHVjNzQwIDJcdWJjODggXHVhZDUwXHVjYzI4XHViODVjXHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtDYXNlICM6JnF1b3Q7IFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgS1x1YWMxY1x1Yzc1OCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1Yjg1YyAoMVx1YmM4OFx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NzQgMlx1YmM4OFx1YzczY1x1Yjg1YyBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjKVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQgS1x1YWMxYyBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SW1wb3NzaWJsZSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4Jm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc2MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEaXNqb2ludCBwYXRocyIsImRlc2NyaXB0aW9uIjoiPHA+T25lIG9mIHlvdXIgY2xhc3NlcyBoYXMgSyBzdHVkZW50cyBpbiBpdCB3aG8gcmVhbGx5IGRvbiZyc3F1bzt0IGxpa2UgZWFjaCBvdGhlci4gSW4gZmFjdCwgdGhleSBkaXNsaWtlIGVhY2ggb3RoZXIgdGhhdCB0aGV5IHdhbnQgdG8gXHVmYjAxbmQgcm91dGVzIHRvIGNsYXNzIHRoYXQgZG9uJnJzcXVvO3QgaW50ZXJzZWN0IHRvIHRoYXQgdGhleSB3b24mcnNxdW87dCBldmVyIHNlZSBlYWNoIG90aGVyIG91dHNpZGUgb2YgY2xhc3MuIENhbiB5b3UgXHVmYjAxbmQgc3VjaCByb3V0ZXM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgXHVmYjAxbGUgd2lsbCBjb250YWluIG11bHRpcGxlIGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCBjYXNlIGlzIEsgTiwgd2hlcmUgSyBpcyB0aGUgbnVtYmVyIG9mIHJvdXRlcyB5b3UgbmVlZCB0byBcdWZiMDFuZCBhbmQgTiBpcyB0aGUgbnVtYmVyIG9mIGludGVyc2VjdGlvbnMgaW4gTUlUJnJzcXVvO3MgXHVmYjAyb29yIHBsYW4uIFRoZSBpbnRlcnNlY3Rpb25zIGFyZSBudW1iZXJlZCAxLCZuYnNwOy4uLiwgTi4gVGhpcyBpcyBmb2xsb3dlZCBieSBOIGxpbmVzLCBvbmUgZm9yIGVhY2ggaW50ZXJzZWN0aW9uLCBjb250YWluaW5nIHRoZSBpbmRpY2VzIG9mIHRoZSBhZGphY2VudCBpbnRlcnNlY3Rpb25zLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAoVGhpcyBtZWFucyB0aGF0IGlmIHRoZSBsaW5lIGZvciBpbnRlcnNlY3Rpb24gMiBjb250YWlucyBhIDMsIHRoZW4gdGhlIGxpbmUgZm9yIGludGVyc2VjdGlvbiAzIHdpbGwgY29udGFpbiBhIDIuKSBFdmVyeSBpbnRlcnNlY3Rpb24gaXMgYWRqYWNlbnQgdG8gYXQgbGVhc3Qgb25lIG90aGVyIGludGVyc2VjdGlvbi48XC9wPlxyXG5cclxuPHA+RWFjaCBjYXNlIGlzIGZvbGxvd2VkIGltbWVkaWF0ZWx5IGJ5IHRoZSBuZXh0IGNhc2UuIFRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBvbmx5ICZsZHF1bzswIDAmcmRxdW87LjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IDEgJmxlOyBLICZsZTsgMTAwIGFuZCAyICZsZTsgTiAmbGU7IDUwMDAuPFwvcD5cclxuXHJcbjxwPlRoZSBzdHVkZW50cyBhbGwgc3RhcnQgYXQgaW50ZXJzZWN0aW9uIDEgYW5kIHRoZWlyIGNsYXNzIGlzIGF0IGludGVyc2VjdGlvbiAyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIG91dHB1dCB0aGUgY2FzZSBudW1iZXIsIGluIHRoZSBmb3JtYXQgJmxkcXVvO0Nhc2UgIzomcmRxdW87LCBmb2xsb3dlZCBieSBhIG5ld2xpbmUuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBLIG5vbi1pbnRlcnNlY3Rpbmcgcm91dGVzIGZyb20gdGhlIHN0YXJ0ICgxKSB0byB0aGUgZW5kICgyKSwgdGhlbiB0aGlzIG11c3QgYmUgZm9sbG93ZWQgSyBsaW5lcywgZWFjaCBvbmUgZ2l2aW5nIGEgbGlzdCBvZiBjb3JuZXJzLCBpbiBvcmRlciwgb24gb25lIHN1Y2ggcm91dGUgZnJvbSAxIHRvIDIuIElmIG5vdCwgdGhlbiBvdXRwdXQgb25lIGxpbmUgd2l0aCB0aGUgd29yZCAmbGRxdW87SW1wb3NzaWJsZSZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPk91dHB1dCBhIGJsYW5rIGxpbmUgYWZ0ZXIgZWFjaCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d