P13446 [GCJ 2009 #3] Football Team

A football team will be standing in rows to have a photograph taken. The location of each player will be given by two integers $x$ and $y$, where $y$ gives the number of the row, and $x$ gives the distance of the player from the left edge of the row. The $x$ values will be all different. In order to make the photo more interesting, you're going to make sure players who are near each other have shirts of different colors. To do this, you set the following rule: For each player $P$: - The closest player to the right of $P$ in the same row, if there is such a player, must have a different shirt color. - The closest player to the right of $P$ in the previous row, if there is such a player, must have a different shirt color. - The closest player to the right of $P$ in the next row, if there is such a player, must have a different shirt color. More formally, if there is a player at $(x_1, y_1)$ and $(x_2, y_2)$, where $x_1 < x_2$, then those two players must have different shirt colors if: - $y_1 - 1 \leq y_2 \leq y_1 + 1$, and - there is no $x_3$ such that there is a player at $(x_3, y_2)$ and $x_1 < x_3 < x_2$. Find the minimum number of distinct shirt colors required so that this is possible.

The first line of input contains a single integer $T$, the number of test cases. Each test case starts with a line that contains an integer $N$, the number of players, followed by $N$ lines of the form $x$ $y$ each specifying the position of one player.

For each test case, output Case #X: $c$ where $X$ is the test case number, starting from 1, and $c$ is the minimum number of colors required.

**Limits** - $1 \leqslant T \leqslant 100$ - $1 \leqslant x \leqslant 1000$ - The values of $x$ will all be different. **Small dataset(8 Pts)** - $1 \leqslant y \leqslant 15$ - $1 \leqslant N \leqslant 100$ **Large dataset(19 Pts)** - $1 \leqslant y \leqslant 30$ - $1 \leqslant N \leqslant 1000$