P13446 [GCJ 2009 #3] Football Team

一支足球队将要分排站好拍照。每位球员的位置由两个整数 $x$ 和 $y$ 给出，其中 $y$ 表示排号，$x$ 表示该球员距离本排左边缘的距离。所有球员的 $x$ 值都互不相同。 为了让照片更有趣，你希望相邻的球员穿不同颜色的球衣。为此，你设定了如下规则： 对于每一个球员 $P$： - 如果 $P$ 这一排中，右侧最近的球员存在，则他们两人的球衣颜色必须不同。 - 如果 $P$ 的上一排中，右侧最近的球员存在，则他们的球衣颜色必须不同。 - 如果 $P$ 的下一排中，右侧最近的球员存在，则他们的球衣颜色必须不同。 更正式地说，若存在球员分别在 $(x_1, y_1)$ 和 $(x_2, y_2)$，且 $x_1 < x_2$，那么当满足以下条件时，这两名球员的球衣颜色必须不同： - $y_1 - 1 \leq y_2 \leq y_1 + 1$，并且 - 不存在 $x_3$ 使得在 $(x_3, y_2)$ 有球员，且 $x_1 < x_3 < x_2$。 请你求出，满足上述要求所需的最少球衣颜色数。

输入的第一行包含一个整数 $T$，表示测试用例数量。每组测试用例的第一行为一个整数 $N$，表示球员数量，接下来 $N$ 行，每行两个整数 $x\ y$，表示一名球员的位置。

对于每组测试用例，输出 Case #X: $c$ 其中 $X$ 是测试用例编号（从 $1$ 开始），$c$ 是所需的最少颜色数。

**限制条件** - $1 \leqslant T \leqslant 100$ - $1 \leqslant x \leqslant 1000$ - 所有 $x$ 值均互不相同。 **小数据集（8 分）** - $1 \leqslant y \leqslant 15$ - $1 \leqslant N \leqslant 100$ **大数据集（19 分）** - $1 \leqslant y \leqslant 30$ - $1 \leqslant N \leqslant 1000$ 翻译由 ChatGPT-4.1 完成。