P13458 [GCJ 2008 #1A] Milkshakes

你经营着一家奶昔店。有 $N$ 种不同口味的奶昔，每种口味可以制作成“麦芽味”或“非麦芽味”。因此，你可以制作 $2N$ 种不同类型的奶昔。 你的每位顾客都有一组喜欢的奶昔类型，只要你准备了他们喜欢的任意一种类型，他们就会满意。每位顾客喜欢的类型中，最多只有一种是“麦芽味”。 你需要制作 $N$ 批奶昔，要求如下： - 每种口味的奶昔只制作一批，该批可以是麦芽味或非麦芽味。 - 对于每位顾客，你至少要制作出一种他们喜欢的奶昔类型。 - 使得麦芽味批次的数量尽可能少。 请判断在上述约束下，是否有可能让所有顾客都满意。如果可以，请给出每种口味应制作成麦芽味还是非麦芽味的方案。 如果存在满足条件的方案，且麦芽味批次数最少，则答案唯一。

第一行包含一个整数 $C$，表示测试用例的数量。 对于每个测试用例，包含如下内容： - 一行包含整数 $N$，表示奶昔口味的数量。 - 一行包含整数 $M$，表示顾客的数量。 - 接下来的 $M$ 行，每行描述一位顾客，格式如下： - 一个整数 $T \geq 1$，表示该顾客喜欢的奶昔类型数量，后跟 - $T$ 对整数“X Y”，每对表示一种该顾客喜欢的类型，其中 $X$ 为口味编号（$1$ 到 $N$），$Y$ 为 $0$ 表示非麦芽味，$1$ 表示麦芽味。 注意： - 对于同一位顾客，不会有重复的“X Y”对。 - 每位顾客至少喜欢一种口味（$T \geq 1$）。 - 每位顾客喜欢的类型中，最多只有一种是麦芽味（即每位顾客最多只有一对 $Y = 1$）。 所有数字之间用单个空格分隔。

共 $C$ 行，每行对应一个测试用例，格式为 "Case #$X$: "，其中 $X$ 为测试用例编号（从 $1$ 开始），后接： - 如果无法满足所有顾客的需求，输出字符串 "IMPOSSIBLE"； - 否则，输出 $N$ 个用空格分隔的整数，分别表示每种口味应制作成非麦芽味（$0$）还是麦芽味（$1$）。

**样例解释** 在第一个样例中，你必须将第 $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 翻译