Description

你经营着一家奶昔店。有 $N$ 种不同口味的奶昔，每种口味可以制作成“麦芽味”或“非麦芽味”。因此，你可以制作 $2N$ 种不同类型的奶昔。

你的每位顾客都有一组喜欢的奶昔类型，只要你准备了他们喜欢的任意一种类型，他们就会满意。每位顾客喜欢的类型中，最多只有一种是“麦芽味”。

你需要制作 $N$ 批奶昔，要求如下：

• 每种口味的奶昔只制作一批，该批可以是麦芽味或非麦芽味。
• 对于每位顾客，你至少要制作出一种他们喜欢的奶昔类型。
• 使得麦芽味批次的数量尽可能少。

请判断在上述约束下，是否有可能让所有顾客都满意。如果可以，请给出每种口味应制作成麦芽味还是非麦芽味的方案。

如果存在满足条件的方案，且麦芽味批次数最少，则答案唯一。

Input Format

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

对于每个测试用例，包含如下内容：

• 一行包含整数 $N$，表示奶昔口味的数量。
• 一行包含整数 $M$，表示顾客的数量。
• 接下来的 $M$ 行，每行描述一位顾客，格式如下：
  • 一个整数 $T \geq 1$，表示该顾客喜欢的奶昔类型数量，后跟
  • $T$ 对整数“X Y”，每对表示一种该顾客喜欢的类型，其中 $X$ 为口味编号（$1$ 到 $N$），$Y$ 为 $0$ 表示非麦芽味，$1$ 表示麦芽味。

注意：

• 对于同一位顾客，不会有重复的“X Y”对。
• 每位顾客至少喜欢一种口味（$T \geq 1$）。
• 每位顾客喜欢的类型中，最多只有一种是麦芽味（即每位顾客最多只有一对 $Y = 1$）。

所有数字之间用单个空格分隔。

Output Format

共 $C$ 行，每行对应一个测试用例，格式为 "Case #$X$: "，其中 $X$ 为测试用例编号（从 $1$ 开始），后接：

• 如果无法满足所有顾客的需求，输出字符串 "IMPOSSIBLE"；
• 否则，输出 $N$ 个用空格分隔的整数，分别表示每种口味应制作成非麦芽味（$0$）还是麦芽味（$1$）。

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

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

Hint

样例解释

在第一个样例中，你必须将第 $1$ 号口味制作成麦芽味，以满足第一个顾客。其他口味都可以制作成非麦芽味。第二个顾客通过第 $2$ 号口味的非麦芽味得到满足，第三个顾客通过第 $5$ 号口味的非麦芽味得到满足。

在第二个样例中，只有一种口味。一位顾客想要麦芽味，另一位想要非麦芽味，无法同时满足两人。

数据范围

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

• $C = 100$
• $1 \leq N \leq 10$
• $1 \leq M \leq 100$

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

• $C = 5$
• $1 \leq N \leq 2000$
• $1 \leq M \leq 2000$

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

由 ChatGPT 4.1 翻译