SP7559 HATEAM - E - 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 = y_2$ - 或者 $y_1 = y_2 - 1$ - 或者 $y_1 = y_2 + 1$ - 并且在 $x_1 < x < x_2$ 之间没有其他球员在 $y_2$ 行上。 请找出能够满足这些条件所需的最少不同颜色的球衣数量。

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例以一个整数 $N$ 开始，表示球员的数量，接下来有 $N$ 行，每行包含两个整数 $x$ 和 $y$，代表一个球员的位置。

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

$$1 \le T \le 100$$ $$1 \le N \le 10^5$$ $$1 \le x, y \le 10^9$$ $x$ 值各不相同。 ### 示例 #### 输入 ``` 3 3 10 10 8 15 12 7 5 1 1 2 1 3 1 4 1 5 1 3 1 1 2 2 3 1 ``` #### 输出 ``` Case #1: 1 Case #2: 2 Case #3: 3 ``` **本翻译由 AI 自动生成**