P13050 [GCJ 2020 Qualification] Parenting Partnering Returns

Cameron 和 Jamie 的孩子快 3 岁了！虽然孩子现在更独立了，但安排孩子的活动和家务对这对夫妇来说仍然是个挑战。 Cameron 和 Jamie 需要共同完成 $\mathbf{N}$ 项当天的活动。每项活动都在一天中的特定时间段进行。他们需要将这些活动分配给两人，确保每人不会被分配到时间重叠的两项活动。注意：一项在时间 $\mathbf{t}$ 结束的活动与另一项在时间 $\mathbf{t}$ 开始的活动不算重叠。 例如，假设 Jamie 和 Cameron 需要安排 3 项活动：第一项从 18:00 到 20:00，第二项从 19:00 到 21:00，第三项从 22:00 到 23:00。一种可能的分配方式是 Jamie 负责第二项活动（19:00-21:00），Cameron 负责另外两项。另一种有效分配是 Cameron 负责第一项活动（18:00-20:00），Jamie 负责另外两项。注意前两项活动在 19:00 至 20:00 期间重叠，因此不能将它们分配给同一个人。 给定每项活动的开始和结束时间，找出任意一个不要求同一人承担重叠活动的排班方案，或者判定这是不可能的。

输入的第一行包含测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示活动数量。接下来 $\mathbf{N}$ 行中，第 $\mathbf{i}$ 行（从 1 开始计数）包含两个整数 $\mathbf{S}_{\mathbf{i}}$ 和 $\mathbf{E}_{\mathbf{i}}$，表示第 $\mathbf{i}$ 项活动从午夜后 $\mathbf{S}_{\mathbf{i}}$ 分钟开始，到午夜后 $\mathbf{E}_{\mathbf{i}}$ 分钟结束。

对于每个测试用例，输出一行 `Case #x: y`，其中 $\mathbf{x}$ 是测试用例编号（从 1 开始），$\mathbf{y}$ 如果不存在有效排班方案则输出 `IMPOSSIBLE`，否则输出一个长度为 $\mathbf{N}$ 的字符串。字符串的第 $\mathbf{i}$ 个字符如果是 $\mathbf{c}$ 表示第 $\mathbf{i}$ 项活动分配给 Cameron，$\mathbf{j}$ 表示分配给 Jamie。 若存在多个解，输出任意一个即可。

**样例解释** 样例 #1 对应题目描述中的情况。如所述，还存在其他有效解，例如 `JCJ` 和 `JCC`。 样例 #2 中，三项活动互相重叠。无论如何分配都会导致至少一人承担两项重叠活动，因此无解。 样例 #3 中，注意 Cameron 在 100 分钟时结束一项活动并立即开始另一项活动。 样例 #4 中，任意分配方案都有效。特别地，允许一人承担所有活动。 **数据范围** - $1 \leq \mathbf{T} \leq 100$； - $0 \leq \mathbf{S}_{\mathbf{i}} < \mathbf{E}_{\mathbf{i}} \leq 24 \times 60$。 **测试集 1（7 分，可见判定）** - $2 \leq \mathbf{N} \leq 10$。 **测试集 2（12 分，可见判定）** - $2 \leq \mathbf{N} \leq 1000$。 翻译由 DeepSeek V3 完成