DISJPATH - Disjoint Paths

One of your classes has K students in it who really don't like each other. In fact, they dislike each other so much that they want to find routes to class that don't cross at any intersection so that they won't ever see each other outside of class. Can you find such routes?

Input

The input file will contain multiple cases. The first line of each case is K N, where K is the number of routes you need to find and N is the number of intersections in MIT's floor plan. The intersections are numbered 1 ... N. This is followed by N lines, one for each intersection, containing the indices of the adjacent intersections, separated by spaces. (This means that if the line for intersection 2 contains a 3, then the line for intersection 3 will contain a 2.) Every intersection is adjacent to at least one other intersection. Each case is followed immediately by the next case. The end of the input is indicated by a line containing only "0 0". You may assume that 1 ≤ K ≤ 100 and 2 ≤ N ≤ 5000. The students all start at intersection 1 and their class is at intersection 2.

Output

For each case, output the case number, in the format "Case #:", followed by a newline. If there are K non-intersecting routes from the start (1) to the end (2), then this must be followed K lines, each one giving a list of corners, in order, on one such route from 1 to 2. If not, then output one line with the word "Impossible". Output a blank line after each test case.

Example

Input:
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

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

Case 2:
Impossible

Added by:Minilek
Date:2008-12-22
Time limit:30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2008

hide comments
2015-06-16 03:44:19 Nathan Benedetto Proença
Internal error is bad =/
2015-05-30 18:14:02 Husam Sami Musleh
Why i'm getting "internal error" ??
2015-02-25 21:26:54 phoenix
Why getting internal error?
2011-11-20 09:41:52 Buda IM (retired)
Was surprised to see AC. MIT grader is easy to trick :)
2011-07-20 00:04:27 Problem Solver
Cool, my output isn't lexicographicaly correct, but got AC :)
2010-08-31 16:45:38 MarioYC
Should say N<=500
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.