NYAB - Arranging New Year Balloons

no tags 

In New Year Dian Prepared a Balloon exhibition. Professor Shiplu as a true Balloon lover visited the Flora exhibition also this year. He was pleased by the most beautiful Balloons and other balloons of the world – Red, green, yallow. All Balloons were nicely arranged.

The Balloon arrangement that was the most appealing to him (at least mathematically) was composed of many kinds of Balloons arranged in a rectangular grid, such that

  • each row of the grid contained each kind of Balloons exactly once and
  • each column of the grid contained each kind of Balloons at most once.

Professor Shiplu is a good mathematician and soon he realized that the number of columns of the grid has to be the same as the number of different kinds of Balloons in the arrangement. But soon he encountered a problem he was unable to solve: He would like to add more rows of Balloons to the arrangement without violating the rules stated above. (Note that he may not modify the existing rows and therefore he may not use any new kinds of Balloons in the new rows.) Help him add as many rows as possible!


The input data set describes several flower arrangements; on the first line their number is given. Each flower arrangement description begins with two positive integers N and M, representing the number of columns and rows of the grid. The different kinds of flowers are represented by numbers 1,2,...,N. The following M lines contain N integers each representing the kinds of flowers in one row of the arrangement.

WHERE 1 N, M 1000


For each flower arrangement print Case No. Next line print K – the maximum number of lines that can be added to the arrangement. Then print K lines containing N numbers each, describing the added rows. The numbers in the output file may be separated by arbitrary whitespaces, e.g. instead of printing one long line containing N numbers you may print several shorter lines containing the same numbers in the same order.
There will be a blank line between two cases and there will not any extra space in every line.





3 2
3 2 1
1 3 2

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

Case 2:
3 2 1 4
4 3 2 1

Added by:Najmuzzaman
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY