Let's start with some definitions. We call the arrangements from the problem
statement *Latin rectangles*. A Latin rectangle with the same number of rows and
columns is called a *Latin square*.

The task was to add as many rows as possible to a Latin rectangle. We will prove that in fact each Latin rectangle can be extended to a Latin square. (This result is one of the "true classics" in combinatorics.)

Here is the argument: Clearly you can't add more than **N-M** rows.
If **M=N**, the Latin rectangle is already a Latin square. Now assume that **M<N**.
We will show how to add one row to the rectangle; repeating this process **N-M** times
leads to the resulting Latin square.

For the arrangement let's construct following bipartite graph **G** with **N+N**
vertices (**N** vertices in each partition): Vertices of the left partition will
correspond to the columns of the grid. Vertices of the right partition will correspond
to various kinds of flowers. The column **X** and a kind of flowers **Y** will
be connected by an edge iff the column **X** doesn't contain the kind **Y** yet.
Clearly each perfect bipartite matching of this graph induces a row of flowers that
can be added to the arrangement and vice versa.

It remains to show that we can always find a prefect matching in the graph **G**. This
follows immediately from Hall's theorem (sometimes called "Marriage theorem"). You may find the
proof in almost any introductory book on combinatorics and/or graph theory.

Theorem (Hall). Let **G** be a bipartite graph with partitions **A, B**.
For a set of vertices **U** we will denote the set of all their neighbors by **N(U)**.
(E.g. **N(U)** contains all vertices connected by an edge to some vertex in **U**.)
A perfect matching in the graph **G** exists iff for all subsets **S** of the partition
**A** (in our case the columns of the rectangle) **|N(S)|>=|S|**. (Here **N(S)** is the set
of colors that may be used at least in one of the selected columns.)

Back to adding a row of flowers. Take an arbitrary set **S** of columns, let **|S|=r**
**(1<=r<=n)**. Each corresponding vertex in our graph has a degree **(N-M)>0**.
Also there are exactly **Q=(N-M)*r** edges leaving the subset **S**. Similarly
each vertex representing a kind of flowers has a degree **(N-M)**. Therefore there are at
least **Q/(N-M)** vertices (i.e. kinds of flowers) connected to **S**.
It follows that **|N(S)| >= Q/(N-M) = r = |S|** and Hall's theorem guarantees us
the existence of a perfect matching.

There are several known algorithms to find a maximum (not necessarily perfect) matching in a
bipartite graph. We will briefly state the most simple of them (as it is already fast enough to
solve the hard input). We will call an edge *matched* if it is a part of the current matching
and *free* otherwise. A vertex can also be *matched* (incident with some edge in the
matching) or *free*. An *augmenting path* is a path with alternating matched and free
edges, starting and ending in free vertices. It can be easily shown that a matching is maximum iff
no augmenting path exists.

The algorithm will work in rounds. In each round we run a breadth-first search to find an augmenting path. If no such path exists, we are done and found a perfect matching. Otherwise we have found a new matching having more edges. This matching can be obtained from the old one by "inverting" all edges on the augmenting path (e.g. matched edges become free and vice versa).

Each time we find a perfect matching, we output the corresponding row of flowers, remove the matched
edges from the graph and start from the beginning. The total running time (using the algorithm
described above to find a matching) is **O(N ^{4})**.

The easy input data set could be solved quickly using a simple backtracking algorithm — an easy way how to get one point.