题目描述

You would like to get your $F$ friends to share some news. You know your friends well, so you know which of your friends can talk to which of your other friends. There are $P$ such one-way relationships, each of which is an ordered pair $(A_i, B_i)$ that means that friend $A_i$ can talk to friend $B_i$. It does not imply that friend $B_i$ can talk to friend $A_i$; however, another of the ordered pairs might make that true.

For every such existing ordered pair $(A_i, B_i)$, you want friend $A_i$ to deliver some news to friend $B_i$. In each case, this news will be represented by an integer value; the magnitude of the news is given by the absolute value, and the type of news (good or bad) is given by the sign. The integer cannot be 0 (or else there would be no news!), and its absolute value cannot be larger than $F^2$ (or else the news would be just too exciting!). These integer values may be different for different ordered pairs.

Because you are considerate of your friends' feelings, for each friend, the sum of the values of all news given by that friend must equal the sum of values of all news given to that friend. If no news is given by a friend, that sum is considered to be 0; if no news is given to a friend, that sum is considered to be 0.

Can you find a set of news values for your friends to communicate such that these rules are obeyed, or determine that it is impossible?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each begins with one line with two integers $F$ and $P$: the number of friends, and the number of different ordered pairs of friends. Then, $P$ more lines follow; the $i$-th of these lines has two different integers $A_i$ and $B_i$ representing that friend $A_i$ can talk to friend $B_i$. Friends are numbered from 1 to $F$.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is either IMPOSSIBLE if there is no arrangement satisfying the rules above, or, if there is such an arrangement, $P$ integers, each of which is nonzero and lies inside $[-F^2, F^2]$. The $i$-th of those integers corresponds to the $i$-th ordered pair from the input, and represents the news value that the first friend in the ordered pair will communicate to the second. The full set of values must satisfy the conditions in the problem statement.

If there are multiple possible answers, you may output any of them.

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

Case #1: 1 1
Case #2: IMPOSSIBLE
Case #3: -1 -1 -1
Case #4: 4 -4 -4 8
Case #5: -1 1 1

提示

Sample Explanation

The sample output shows one possible set of valid answers. Other valid answers are possible.

In Sample Case #1, one acceptable arrangement is to have friend $1$ deliver news with value $1$ to friend $2$, and vice versa.

In Sample Case #2, whatever value of news friend $1$ gives to friend $2$, it must be nonzero. So, the sum of news values given to friend $2$ is not equal to zero. However, friend $2$ cannot give any news and so that value is $0$. Therefore, the sums of given and received news for friend $2$ cannot match, and the case is IMPOSSIBLE.

In Sample Case #3, each of friends $1, 2$, and $3$ can deliver news with value $-1$ to the one other friend they can talk to — an unfortunate circle of bad news! Note that there is a friend 4 who does not give or receive any news; this still obeys the rules.

In Sample Case #4, note that $-5\ 5\ 5\ -10$ would not have been an acceptable answer, because there are $3$ friends, and $|-10| > 3^2$.

In Sample Case #5, note that the case cannot be solved without using at least one negative value.

Limits

• $1 \leq T \leq 100$.
• $1 \leq A_i \leq F$, for all $i$.
• $1 \leq B_i \leq F$, for all $i$.
• $A_i \neq B_i$, for all $i$. (A friend does not self-communicate.)
• $(A_i, B_i) \neq (A_j, B_j)$, for all $i \neq j$. (No pair of friends is repeated within a test case in the same order.)

Small dataset (Test Set 1 - Visible)

• Time limit: 20 5 seconds.
• $2 \leq F \leq 4$.
• $1 \leq P \leq 12$.

Large dataset (Test Set 2 - Hidden)

• Time limit: 40 10 seconds.
• $2 \leq F \leq 1000$.
• $1 \leq P \leq 2000$.