405722: GYM102055 I Cockroaches

There are $$$N$$$ cockroaches in the field. Cockroach $$$i$$$ is located at coordinate $$$(x_i, y_i)$$$. No two cockroaches are located at the same spot. Boss Luo has a powerful pesticide that can instantly kill all cockroaches on the horizontal and vertical line of the spot where it is used. i.e. cockroaches with either the same x coordinate or y coordinate as the pesticide spot will be killed.

Boss Luo wonders how many cockroaches can be killed at most when the pesticide is used in one spot. He is also interested in the number of different subsets of the annihilated cockroaches when the pesticide kills most cockroaches.

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 100$$$). $$$T$$$ test cases follow.

For each test case, the first line contains an integers $$$N$$$ ($$$1 \le N \le 10^5$$$), the number of cockroaches.

The next $$$N$$$ lines each contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^9$$$), describing the coordinates of the cockroaches.

For at least 80 test cases, it is guaranteed that $$$N \leq 5\,000$$$.

For each test case, output one line containing "Case x: y z", where x is the test case number (starting from $$$1$$$), y is the maximum number of cockroaches that can be killed with pesticide applied on one spot, and z is the number of different subsets of the annihilated cockroaches when the pesticide kills most cockroaches.

2
5
1 2
1 3
2 3
4 5
6 7
3
1 2
2 3
3 1

Case 1: 3 5
Case 2: 2 3

For test case 1, 3 cockroaches can be killed if the pesticide is used optimally. There are 5 possible subsets: $$$\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{2, 3, 4\}, \{2, 3, 5\}$$$.

For test case 2, 2 cockroaches can be kill at best. All subsets with 2 cockroaches are possible: $$$\{1, 2\}, \{1, 3\}, \{2, 3\}$$$.