你希望你的 $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$ 行；其中第 $i$ 行包含两个不同的整数 $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 \le T \le 100$ $1 \le A_i \le F$ $1 \le B_i \le F$ $A_i \neq B_i$（朋友不会与自己交谈） $(A_i, B_i) \neq (A_j, B_j)$，对于所有 $i \neq j$（在同一个测试用例中，朋友对的顺序不会重复）

子任务 1

时间限制：10 秒 $2 \le F \le 4$ $1 \le P \le 12$

子任务 2

时间限制：20 秒 $2 \le F \le 1000$ $1 \le P \le 2000$

样例

样例输入 1

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

样例输出 1

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

说明

样例输出展示了一种可能的有效答案集合。其他有效的答案也是可能的。

在样例 1 中，一种可接受的安排是让朋友 1 向朋友 2 传递值为 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 中，注意如果不使用至少一个负值，该情况无法解决。