Description

你需要雇佣一些人来粉刷一段栅栏。这段栅栏由 $10000$ 个连续的部分组成，编号从 $1$ 到 $10000$。

你收到了几位油漆工的报价，每位油漆工提出用某种特定颜色粉刷一段连续的栅栏部分。你需要选择一组报价，使得：

• 每一段栅栏都被粉刷。
• 使用的颜色不超过 $3$ 种。

如果可以满足上述两个要求，求你最少需要接受多少个报价。

Input Format

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

对于每个测试用例，包含：

• 一行一个整数 $N$，表示报价的数量。
• 接下来的 $N$ 行，每行包含 "$C$ $A$ $B$"，其中 $C$ 是颜色（由不超过 $10$ 个大写字母组成的字符串），$A$ 是要粉刷的起始部分编号，$B$ 是要粉刷的结束部分编号。$1 \leq A \leq B \leq 10000$。

Output Format

• 共 $T$ 行，每行对应一个测试用例，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号，$Y$ 是需要接受的最少报价数量。如果不存在可行的报价组合，则输出 "Case #$X$: IMPOSSIBLE"。

5
2
BLUE 1 5000
RED 5001 10000
3
BLUE 1 6000
RED 2000 8000
WHITE 7000 10000
4
BLUE 1 3000
RED 2000 5000
ORANGE 4000 8000
GREEN 7000 10000
2
BLUE 1 4000
RED 4002 10000
3
BLUE 1 6000
RED 4000 10000
ORANGE 3000 8000

Case #1: 2
Case #2: 3
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: 2

Hint

样例说明

在第一个测试用例中，接受两个报价可以刚好粉刷整段栅栏，每人各粉刷 $5000$ 段，且没有重叠。

在第二个测试用例中，油漆工的粉刷范围有重叠，这是允许的。

在第三个测试用例中，接受全部四个报价可以覆盖整段栅栏，但会用到 $4$ 种不同的颜色，因此不满足条件。

在第四个测试用例中，第 $4001$ 段无法被粉刷。

在第五个测试用例中，只需接受第一个和第二个报价即可成功粉刷整段栅栏。

数据范围

• $1 \leq T \leq 50$

小数据范围（7 分，测试集 1 - 可见）

• $1 \leq N \leq 10$

大数据范围（13 分，测试集 2 - 隐藏）

• $1 \leq N \leq 300$

由 ChatGPT 4.1 翻译