P13176 [GCJ 2017 #3] Good News and Bad News

你希望让你的 $F$ 个朋友之间互相传递一些消息。你非常了解你的朋友们，因此你知道哪些朋友可以和哪些其他朋友交流。共有 $P$ 个这样的单向关系，每个关系是一个有序对 $(A_i, B_i)$，表示朋友 $A_i$ 可以和朋友 $B_i$ 交流。这并不意味着朋友 $B_i$ 也可以和朋友 $A_i$ 交流；不过，另一个有序对可能会使得这种情况成立。 对于每一个存在的有序对 $(A_i, B_i)$，你希望朋友 $A_i$ 向朋友 $B_i$ 传递一条消息。每条消息用一个整数值表示；消息的大小由其绝对值给出，消息的类型（好消息或坏消息）由其符号给出。整数不能为 $0$（否则就没有消息了！），并且其绝对值不能大于 $F^2$（否则消息就太激动人心了！）。这些整数值对于不同的有序对可以不同。 因为你很关心朋友们的感受，对于每个朋友，所有由该朋友发出的消息的值之和，必须等于所有传递给该朋友的消息的值之和。如果某个朋友没有发出任何消息，则该和视为 $0$；如果某个朋友没有收到任何消息，该和也视为 $0$。 你能否为你的朋友们找到一组满足上述规则的消息值，或者判断这是不可能的？

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试用例。每组测试用例的第一行为两个整数 $F$ 和 $P$，分别表示朋友的数量和不同的有序朋友对的数量。接下来的 $P$ 行，每行有两个不同的整数 $A_i$ 和 $B_i$，表示朋友 $A_i$ 可以和朋友 $B_i$ 交流。朋友编号从 $1$ 到 $F$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 要么是 IMPOSSIBLE（如果不存在满足条件的方案），要么是 $P$ 个整数，每个都非零且在区间 $[-F^2, F^2]$ 内。这 $P$ 个整数中的第 $i$ 个对应输入中的第 $i$ 个有序对，表示第一个朋友向第二个朋友传递的消息值。所有消息值的集合必须满足题目中的所有条件。 如果有多组可行解，你可以输出其中任意一组。

**样例解释** 样例输出展示了一组可行答案。其他可行答案也是允许的。 在样例第 1 组中，一种可接受的方案是让朋友 $1$ 向朋友 $2$ 传递值为 $1$ 的消息，朋友 $2$ 向朋友 $1$ 传递值为 $1$ 的消息。 在样例第 2 组中，无论朋友 $1$ 向朋友 $2$ 传递什么非零消息，朋友 $2$ 收到的消息之和都不是 $0$。但朋友 $2$ 无法向任何人传递消息，因此其发出的消息之和为 $0$。所以朋友 $2$ 发出和收到的消息之和无法相等，因此该组为 IMPOSSIBLE。 在样例第 3 组中，朋友 $1, 2, 3$ 各自向能交流的朋友传递值为 $-1$ 的消息——形成了一个不幸的坏消息循环！注意，朋友 $4$ 既不发出也不接收任何消息，这同样满足规则。 在样例第 4 组中，$-5\ 5\ 5\ -10$ 不是一个可接受的答案，因为有 $3$ 个朋友，且 $|-10| > 3^2$。 在样例第 5 组中，必须至少使用一个负值才能得到可行解。 **数据范围** - $1 \leq T \leq 100$。 - 对所有 $i$，$1 \leq A_i \leq F$。 - 对所有 $i$，$1 \leq B_i \leq F$。 - 对所有 $i$，$A_i \neq B_i$。（朋友不会和自己交流。） - 对所有 $i \neq j$，$(A_i, B_i) \neq (A_j, B_j)$。（同一组测试用例中不会有重复的有序对。） **小数据集（测试集 1 - 可见）** - 时间限制：~~20~~ 5 秒。 - $2 \leq F \leq 4$。 - $1 \leq P \leq 12$。 **大数据集（测试集 2 - 隐藏）** - 时间限制：~~40~~ 10 秒。 - $2 \leq F \leq 1000$。 - $1 \leq P \leq 2000$。 由 ChatGPT 4.1 翻译