Good News and Bad News (Large)

You want to get your $F$ friends to share some news. You know your friends well, so you know which of them can talk to which. There are $P$ one way relationships, and the $i$-th of them 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 state that separately.

For every given ordered pair $(A_i, B_i)$, friend $A_i$ has to deliver one piece of news to friend $B_i$. A piece of news is one integer. Its absolute value is the magnitude of the news, and its sign gives the type of the news. The integer cannot be 0 (there would be no news at all), and its absolute value cannot exceed $F^2$ (the news would be too exciting). Different ordered pairs may get different integers.

Because you care about your friends' feelings, for each friend the sum of the values of all news that friend delivers has to equal the sum of the values of all news that friend receives. If a friend delivers no news, that sum is 0. If a friend receives no news, that sum is 0.

Find a set of news values that obeys every rule, or determine that none exists.

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains two integers $F$ and $P$, the number of friends and the number of ordered pairs of friends. Each of the next $P$ lines contains 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 1000$
• $1 \le P \le 2000$
• $1 \le A_i \le F$, $1 \le B_i \le F$, $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, print one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is one of the following.

If no assignment obeys the rules, $y$ is IMPOSSIBLE.

Otherwise $y$ is $P$ integers separated by single spaces, and the $i$-th of them is the news value that friend $A_i$ delivers to friend $B_i$. Many assignments obey the rules, so print exactly the one that this procedure builds.

1. Build an undirected multigraph whose vertices are friends 1 to $F$ and whose $i$-th edge joins $A_i$ and $B_i$. Edge numbers follow the input order.
2. Run a depth first search over that multigraph. Start at the smallest friend that has not been visited yet, and repeat until every friend is visited. At a friend, examine the incident edges in increasing order of edge number, and skip the single edge that was used to enter that friend. An edge that leads to a friend not visited yet becomes a tree edge of the search forest, and every other edge joins some friend to one of its ancestors and is a back edge.
3. Let back edge $i$ join friend $u$ and its ancestor $w$. Send one unit of news around the cycle formed by edge $i$ and the forest path that goes down from $w$ to $u$. The unit travels from $u$ to $w$ along edge $i$, and from $w$ toward $u$ along the forest path.
4. Once every back edge is handled, the value of edge $i$ is the total amount that travelled along it, counted as positive when it travelled from $A_i$ to $B_i$ and as negative when it travelled from $B_i$ to $A_i$.

Whenever an assignment that obeys the rules exists, the values this procedure builds are nonzero and lie inside $[-F^2, F^2]$.

A friend who neither delivers nor receives any news still obeys the rules.

If some friend only receives news and can talk to nobody, the test case is IMPOSSIBLE. A news value cannot be 0, so the sum received is nonzero while the sum delivered is 0.

A value whose absolute value exceeds $F^2$ is not allowed even when every other rule holds.

Some test cases cannot be solved without at least one negative value.