Milkshakes (Large)

You run a milkshake shop. You can prepare $N$ flavors, and each flavor is prepared either malted or unmalted, so there are $2N$ possible milkshake types.

Every customer has a set of types they like. That customer is satisfied if you prepare at least one type from the set. At most one of the types a customer likes is malted.

You prepare $N$ batches under these conditions.

• You make exactly one batch per flavor, and that batch is either malted or unmalted.
• Every customer receives at least one type they like.
• The number of malted batches is as small as possible.

Decide whether all customers can be satisfied, and if they can, report which types to prepare. When they can be satisfied, exactly one choice minimizes the number of malted batches.

The first line has an integer $C$, the number of test cases. Each test case is given in this format.

• A line with $N$, the number of flavors.
• A line with $M$, the number of customers.
• $M$ lines, one per customer. Each line starts with $T$, the number of types that customer likes, followed by $T$ pairs of integers "$X$ $Y$" describing those types. $X$ is a flavor number from $1$ to $N$, and $Y$ is $0$ for unmalted or $1$ for malted.

Numbers on the same line are separated by single spaces.

Limits

• $1 \le C \le 5$
• $1 \le N \le 2000$
• $1 \le M \le 2000$
• $T \ge 1$, and no pair appears twice for a single customer
• At most one of the types a customer likes is malted (at most one pair with $Y = 1$)
• The sum of $T$ over all customers of one test case is at most $3000$

Print $C$ lines, one per test case in input order. Line $X$ starts with Case #X: and continues with one of the following.

• IMPOSSIBLE, if the customers cannot all be satisfied.
• Otherwise, $N$ space-separated integers, one for each flavor from $1$ to $N$. A flavor prepared unmalted is $0$, and a flavor prepared malted is $1$.

In the first test case of the first example, the first customer forces flavor 1 to be malted. Every other flavor stays unmalted. The second customer is satisfied by flavor 2 unmalted, and the third customer by flavor 5 unmalted.

In the second test case there is only one flavor. One customer wants it malted and the other wants it unmalted, so the two cannot both be satisfied.