你拥有一家奶昔店。 共有 $N$ 种不同的口味，每种口味都可以制作成“麦芽”或“非麦芽”两种版本。 因此，你总共可以制作 $2N$ 种不同的奶昔。

每位顾客都有自己喜欢的奶昔类型集合，只要你制作的奶昔中至少有一种是他们喜欢的，他们就会感到满意。 每位顾客喜欢的类型中，最多只有一种是“麦芽”口味。

你需要制作 $N$ 批奶昔，要求满足以下条件：

• 每种口味的奶昔恰好制作一批，且必须是麦芽或非麦芽中的一种。
• 对于每位顾客，你制作的奶昔中至少有一种是他们喜欢的。
• 麦芽口味的批次数量尽可能少。

请判断在给定这些约束条件下是否能够满足所有顾客的需求，如果可以，请给出你应该制作的奶昔类型。

如果能够满足所有顾客，那么在最小化麦芽口味批次数量的前提下，答案是唯一的。

输入格式

第一行包含一个整数 $C$，表示输入文件中的测试用例数量。

对于每个测试用例： 第一行包含一个整数 $N$，表示奶昔口味的数量。 第二行包含一个整数 $M$，表示顾客的数量。 接下来的 $M$ 行，每行代表一位顾客，包含： 一个整数 $T \ge 1$，表示该顾客喜欢的奶昔类型数量，随后是 $T$ 对整数 "$X \ Y$"，表示该顾客喜欢的每种类型，$X$ 是 $1$ 到 $N$ 之间的奶昔口味编号，$Y$ 为 $0$ 表示非麦芽，$1$ 表示麦芽。 注意： 对于同一位顾客，不会出现重复的类型对。 每位顾客至少喜欢一种口味 ($T \ge 1$)。 每位顾客最多喜欢一种麦芽口味（即每位顾客的类型对中，最多只有一对满足 $Y = 1$）。 所有数字均以空格分隔。

输出格式

输出 $C$ 行，每行对应输入文件中的一个测试用例，格式为 "Case #$X$: "，其中 $X$ 是测试用例的编号（从 1 开始），随后是： 如果无法满足顾客的需求，输出字符串 "IMPOSSIBLE"；或者 输出 $N$ 个以空格分隔的整数，分别对应从 $1$ 到 $N$ 的每种口味，若该口味应制作成非麦芽则为 $0$，若应制作成麦芽则为 $1$。

数据范围

小数据集（测试集 1 - 可见；10 分）

$C = 100$

$1 < N < 10$

$1 < M < 100$

大数据集（测试集 2 - 隐藏；25 分）

$C = 5$

$1 < N < 2000$

$1 < M < 2000$

单个测试用例中所有顾客的 $T$ 值之和不超过 $3000$。

样例

样例输入 1

2
5
3
1 1 1
2 1 0 2 0
1 5 0
1
2
1 1 0
1 1 1

样例输出 1

Case #1: 1 0 0 0 0
Case #2: IMPOSSIBLE