Milkshakes (Small)

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

Each customer has a set of milkshake types they like, and a customer is satisfied if you have prepared at least one type from that set. At most one of the types a customer likes is malted.

You want to make $N$ batches of milkshakes so that all of the following hold.

• There is exactly one batch for each flavor, and that batch is either malted or unmalted.
• For each customer, you make at least one type that the customer likes.
• The number of malted batches is as small as possible.

Decide whether you can satisfy every customer, and if you can, find which types you should make.

When every customer can be satisfied, the assignment that minimizes the number of malted batches is unique.

The first line contains the number of test cases $C$.

Each test case is given as follows.

• The first line contains the number of milkshake flavors $N$.
• The second line contains the number of customers $M$.
• Each of the next $M$ lines describes one customer. The line starts with the number of types that customer likes, $T$, followed by $T$ integer pairs $X\ Y$. Here $X$ is a flavor number between $1$ and $N$, and $Y$ is $0$ for unmalted or $1$ for malted.

All numbers on a line are separated by single spaces.

Limits

• $1 \le C \le 100$
• $1 \le N \le 10$
• $1 \le M \le 100$
• $T \ge 1$
• Within one customer, the same pair $(X, Y)$ never appears twice.
• Among the types one customer likes, at most one pair has $Y = 1$.

Print $C$ lines, one per test case, in the order the test cases are given. Each line starts with Case #X: , where $X$ is the test case number starting from $1$. After that prefix, print the following.

• Print IMPOSSIBLE if the customers' preferences cannot all be satisfied.
• Otherwise print $N$ integers separated by spaces, one for each flavor from $1$ to $N$. The integer is $0$ if that flavor should be prepared unmalted and $1$ if it should be prepared malted.

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

The second test case has only one flavor. One customer likes it malted and the other likes it unmalted, so you cannot satisfy both.