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:
More formally, if there is a player at (x1,y1) and (x2,y2), where x1<x2, then those two players must have different shirt colors if:
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 yeach specifying the position of one player.
For each test case, output
Case #X: c
1 ≤ y ≤ 30
1 ≤ N ≤ 1000
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
Migrated from old NTUJ.
google codejam 2009 round 3
| No. | Testdata Range | Score |
|---|