Description

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 期间重叠，因此不能将它们分配给同一个人。

给定每项活动的开始和结束时间，找出任意一个不要求同一人承担重叠活动的排班方案，或者判定这是不可能的。

Input Format

输入的第一行包含测试用例数量 $\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}}$ 分钟结束。

Output Format

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

若存在多个解，输出任意一个即可。

4
3
360 480
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440

Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC

Hint

样例解释

样例 #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 完成