Partitioning Sets with Similarity Constraints

You are given K sets of positive integers. The i-th set contains s_i elements; each element is a positive integer not exceeding n. Two sets A and B are defined to be similar if and only if one of the following holds:

• A and B are equal, or
• When A has one element removed or one element modified (changed to a different value), the resulting set equals B.

In other words, if we denote by \(A\Delta B\) the symmetric difference between A and B, then for two sets of equal size they are similar if \(|A \Delta B| = 0\) or \(|A \Delta B| = 2\) (the latter corresponding to a one‐element modification), and if their sizes differ by one they are similar provided that the smaller is a subset of the larger (corresponding to a deletion).

Your task is to partition the K sets into at most M groups (where it is given that \(M > n\)) so that within each group no two sets are similar. If a valid grouping exists, output any one valid assignment of group numbers to the sets; otherwise, output impossible.

Note: The input guarantees that every number is positive and does not exceed n. There may be multiple valid answers; any valid grouping will be accepted.

The similarity relation can be formalized in \(\LaTeX\) as follows:

[ A \sim B \iff \begin{cases} A = B, \[5mm] \text{or } \left(|A| = |B| \text{ and } |A \Delta B| = 2 \right), \[5mm] \text{or } \left(|A| = |B| + 1 \text{ and } B \subset A \right), \[5mm] \text{or } \left(|B| = |A| + 1 \text{ and } A \subset B \right). \end{cases} ]

inputFormat

The first line contains three integers: K, n, and M. Here, K is the number of sets, n is the maximum value any element can have, and M is the maximum number of groups allowed (with (M > n)).

Each of the following K lines describes a set. Each line begins with an integer s (the size of the set) followed by s positive integers (each not exceeding n).

outputFormat

If a valid grouping exists, output a single line with K integers separated by spaces. The i-th integer represents the group number (an integer from 1 to M) assigned to the i-th set. If no valid grouping exists, output the string impossible.

sample

3 5 6
3 1 2 3
3 1 2 4
2 1 3

1 2 2