P13483 [GCJ 2008 EMEA SemiFinal] Painting a Fence

你需要雇佣一些人来粉刷一段栅栏。这段栅栏由 $10000$ 个连续的部分组成，编号从 $1$ 到 $10000$。 你收到了几位油漆工的报价，每位油漆工提出用某种特定颜色粉刷一段连续的栅栏部分。你需要选择一组报价，使得： - 每一段栅栏都被粉刷。 - 使用的颜色不超过 $3$ 种。 如果可以满足上述两个要求，求你最少需要接受多少个报价。

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

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

**样例说明** 在第一个测试用例中，接受两个报价可以刚好粉刷整段栅栏，每人各粉刷 $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 翻译