Who Brings the Cookies?

Farmer John's $N$ cows, numbered $1$ through $N$, form $M$ study groups. Study group $i$ has $S_i$ member cows (a single cow may belong to several study groups).

For every study group, exactly one of its member cows must be chosen to bring cookies to that group's meeting. Cookies are expensive and take effort to prepare, so the cows want to share the burden as evenly as possible.

Suppose a cow belongs to study groups whose sizes are $c_1, c_2, \dots, c_K$ (that is, she is a member of $K$ groups, and the $j$-th of them has $c_j$ members in total). Then she is willing to bring cookies to at most

$\left\lceil \frac{1}{c_1} + \frac{1}{c_2} + \cdots + \frac{1}{c_K} \right\rceil$

meetings.

Assign to each study group the one cow that will bring its cookies, so that no cow is assigned more meetings than she is willing to bring.

Constraints: $1 \le N \le 1000$, $1 \le M \le 100$, and $1 \le S_i \le 19$.

• Line 1: two space-separated integers $N$ and $M$.
• Lines 2 to $M+1$: line $i+1$ describes study group $i$ as $S_i$ followed by the $S_i$ member cow numbers $G_{i,1}, G_{i,2}, \dots, G_{i,S_i}$, all space-separated.

Print $M$ lines. Line $i$ contains $a_i$, the number of the cow who brings cookies to study group $i$.

Several valid assignments may exist, so output the lexicographically smallest one: make $a_1$ as small as possible; among all assignments with that $a_1$, make $a_2$ as small as possible; and so on.

If no valid assignment exists, print a single line containing $-1$ instead.

The limit counts how expensive a cow's meetings are: a member of a large group contributes little (its cost $1/c$ is small), so she can afford more meetings.

For instance, take a cow that belongs to groups of sizes $2$, $3$, and $1$. Her limit is $\left\lceil \tfrac{1}{2} + \tfrac{1}{3} + \tfrac{1}{1} \right\rceil = \lceil 1.833\ldots \rceil = 2$, so she is willing to bring cookies to at most $2$ meetings. A cow in two groups of size $3$ has limit $\left\lceil \tfrac{1}{3} + \tfrac{1}{3} \right\rceil = 1$.