Henry is a student in Incredible College of Programming and Computers.
One day, he feels hungry during a boring class.
In fact, not only Henry but also his friends are hungry.
They are strongly desired to skip the class and go to the restaurant in the college immediately.
However, they cannot go together because in that way they would easily be caught by the guard,
who would be very happy to send students to Disciplinary Committee.
To avoid attention from the guard, Henry and his friends will go separately.
They would like K routes and each of the routes should be disjoint from others.
A route is a sequence of intersections where two consecutive intersections are connected by at least one road.
Two routes are disjoint if they share neither common roads nor common intersections (except the classroom and the restaurant).
They are not sure whether such many routes exist.
Can you help them?
Warn: 本題有 specialjudge
The input contains multiple test 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 Henry's college.
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.
The input guarantees that the adjacency information is symmetric.
Every intersection is adjacent to at least one other intersection.
The number of times that an index appears in a line indicates the number of roads connecting the two intersections.
Henry's classroom is at intersection 1, and the restaurant is at intersection 2.
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.
For each test case, please output the case number in the format "Case #:" in one line.
If there are K disjoint routes from Henry's classroom to the restaurant,
then output K lines after the case number, each one giving a list of intersections, in order, on one such route.
If not, then output one line with the word "Impossible".
Please output a blank line after each test case.
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
Migrated from old NTUJ.
MIT Individual 2008
| No. | Testdata Range | Score |
|---|