Submit Best Submissions All Submissions

128. Museum Security

Problem Statement:
Square shaped museum, consisting of n by n squared rooms, featuring thousands of rare and precious pieces, making it a target for many thieves who will try to steal its contents.
Security experts met to put some plan to protect the most important pieces in the museum, and agreed to put guards on each valuable piece and thus ensure not to be robbed, but soon they found that they need an army of guards to be able to achieve their goal.
One expert in the area of security suggested that monitoring cameras can do the work, although one simple approach is to associate one camera to each precious piece is a feasible solution, but the expert believes that there should be a more elegant solution with a minimum number of cameras. The expert noticed that all rooms reside on a diagonal has a perfect angel and can be monitored by one camera, also he noticed that unimportant pieces unlike the precious ones are surrounded by some bad quality glass protectors which according to the diagonal monitoring angel prevent a clear sight of the next room.
Given the locations of the precious pieces, and assuming that other locations is filled or can be filled at any time with unimportant pieces, your task is to help the security expert to find the minimum number of cameras (which can be placed in any room) needed to implement his plan.

Input Format:
The first line contains one integer t ≤ 100 which is the number of test cases.
For each test case, the first line contains two integers n and k, n ≤ 100 is the dimension of the square museum and k ≤ n*n the number of target squares where precious pieces are located, the next k lines, each one contains two integers (1 ≤ x, y ≤ n) the location of a precious piece in the museum.

Output Format:
For each input scenario, output a line specifying the minimum number of cameras needed to monitor all of the precious pieces.

Sample Input:
2 5 5 1 1 2 2 2 1 1 2 3 3 10 4 1 1 4 4 2 6 8 8

Sample Output:
2 4

Added by: samiemad
Added at: 2014-02-26 01:15:08 UTC
Time Limit: 5 seconds
Partial score: No
Source:ACM Syrian Collegiate Programming Contest 2013