Good News and Bad News (Small)

You want your $F$ friends to pass news around. You already know which of your friends can talk to which other friends. There are $P$ such one way relationships, and each one is an ordered pair $(A_i, B_i)$ meaning that friend $A_i$ can talk to friend $B_i$. It does not mean that friend $B_i$ can talk to friend $A_i$, although another ordered pair may say exactly that.

For every ordered pair $(A_i, B_i)$ in the input, friend $A_i$ delivers one piece of news to friend $B_i$. Each piece of news is a single integer. The absolute value is the magnitude of the news, and the sign is the type of the news, good or bad. The integer cannot be 0, because then there would be no news, and its absolute value cannot be larger than $F^2$, because then the news would be too exciting. Different ordered pairs may use different values.

You are considerate of your friends' feelings, so for each friend the sum of the values of all news delivered by that friend must equal the sum of the values of all news delivered to that friend. If a friend delivers no news, that sum is 0. If a friend receives no news, that sum is 0.

Decide whether a set of news values obeying all of these rules exists, and find it when it does.

The first line contains the number of test cases $T$. Each test case begins with one line holding two integers $F$ and $P$: the number of friends and the number of ordered pairs. Then $P$ lines follow, and the $i$-th of them holds two different integers $A_i$ and $B_i$, meaning that friend $A_i$ can talk to friend $B_i$. Friends are numbered from 1 to $F$.

Limits

• $1 \le T \le 100$
• $2 \le F \le 4$
• $1 \le P \le 12$
• $1 \le A_i \le F$, $1 \le B_i \le F$ and $A_i \ne B_i$ for all $i$ (a friend does not talk to themselves)
• $(A_i, B_i) \ne (A_j, B_j)$ for all $i \ne j$ (no ordered pair repeats inside one test case)

For each test case, output one line containing Case #x: y, where x is the test case number starting from 1. If no arrangement obeys the rules, y is IMPOSSIBLE. Otherwise y is $P$ integers separated by single spaces, where the $i$-th integer corresponds to the $i$-th ordered pair of the input and is the news value that the first friend of that pair delivers to the second friend. Each integer must be nonzero and lie inside $[-F^2, F^2]$, and the whole set of values must satisfy every condition in the statement.

When several arrangements satisfy the conditions, output only the lexicographically smallest one. Compare $(y_1, y_2, \dots, y_P)$ as sequences of integers, position by position, so the sequence with the smaller value at the first differing position is smaller. For example $(-4, -4)$ is smaller than $(-4, -3)$, and $(-1, 5)$ is smaller than $(1, -5)$.

• If a friend receives news but delivers none, the sum received is nonzero while the sum delivered is 0, so the rules cannot be satisfied.
• A friend who neither delivers nor receives any news breaks no rule.
• Some inputs cannot be solved with positive values only. Those inputs need at least one negative value.
• The bound on the absolute value depends on the number of friends. With 3 friends, $F^2 = 9$, so the value $-10$ is not allowed.