Graceful Matrix
Problem Description
In Matrix Science, Unit Matrix (UM) is a matrix in which the elements on diagonal are all 1, while others are all 0.
Based on Unit Matrix, we define Basic Matrix and Graceful Matrix:
1.Basic Matrix (BM), BM_i means swap the i-th rows and (i+1)-th rows in the Unit Matrix. (0 based)
2.Graceful Matrix (GM), means in every rows and every columns, there is one and only one 1, while others are all 0.
Now we also have a graceful problem, given a GM whose size is N, you need find a BM sequence. At first, the matrix is a UM, by multiplying the matrix one by one in the BM’s sequence order we can get the GM finally. You needn’t find the shortest sequence, but the sequence’s length can’t exceed the number of elements in GM.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with an integer N, indicating the GM’s size.
Then N lines follow, each line contains N integers, 1 or 0, indicating the GM.
You can assume the input Matrix is always graceful.
Technical Specification
- 1 <= T <= 50
- 2 <= N <= 1000
Output
For each test case, output the case number first, then the length of the sequence T your answer will give. Then follow T integers Ai, indicating BM_Ai, the sequence. If the length is zero, just output a blank line.
Make sure your output BM_Ai never exceeds the Input N minus 1, because it doesn't make any sense.
This is a Special Judge problem, so your format should not make any mistake. You can refer to the sample output for more information.
Sample Input
3
2
1 0
0 1
2
0 1
1 0
4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
Sample Output
Case 1: 0
Case 2: 1
0
Case 3: 2
0 2