3342번 - Lanterns 다국어

The parents of Hansel and Gretel would like to take their children out on a walk by night through the forest. Family hiking trips are a cherished family tradition, but Hansel and Gretel do not walk as fast as their parents. During previous walks, they therefore often lost track of them, causing them to be left on their own. At night the forest is a scary place, with predators lurking everywhere. Therefore, it is not hard to understand the children are not particularly looking forward to this walk.

Hansel and Gretel, who do not have GPS facilities, decide to prepare themselves for the walk by bringing lanterns to the forest by day. They can attach these lanterns to trees in the forest. At night, each lantern will then provide a circular spot of light (shadow effects are not taken into account). As predators do not like light, Hansel and Gretel will not be devoured as long as they will stay within the light provided by the lanterns. If they will attach lanterns to trees in the forest that are situated close enough to each other, the corresponding light spots will touch or overlap. This way, a light zone encompassing multiple trees is created, in which they can walk safely. First of all, Hansel and Gretel wonder how many trees can at most be illuminated in one connected light zone (the 'largest connected light zone' in terms of illuminated trees). If the largest connected light zone consists of multiple trees, there will only be one zone in the forest with this maximal number of trees.

Of course Hansel and Gretel can attach lanterns to all trees in this zone, but if trees are situated really close to each other, the light spot of one tree can actually already illuminate the other tree. Therefore, Hansel and Gretel might be able to bring less lanterns without reducing the number of trees they can see and reach in the lighted zone. As this reduces the weight to carry ánd the amounts of light pollution and emitted CO2, they now also are very interested in the smallest number of lanterns needed to illuminate all trees in the largest connected light zone, while maintaining the possibility to reach any tree in this zone from any other tree without having to step into the dark (see Figure 1 for an illustration). Poor Hansel and Gretel do not just lack GPS facilities, they also don't have a computer in their log cabin. You do, so maybe you can help them.

Figure 1: Two possible tree situations. On the left, at most three trees can be illuminated in one light zone. Just one lantern is necessary to achieve this: it should be attached to tree B. On the right, at most four trees can be illuminated in one light zone; the most efficient way to do is is attaching lanterns to trees C and E. In both cases, tree D is situated too far from the other trees to be able to form a light zone with them.

• The first line of input consists of the integer number n (0 < n ≤ 100), the number of test cases;
• Then, for each test case:
  • A line with an integer number r (0 < r ≤ 100), which is the radius of the circular light spot that the lanterns create when illuminated;
  • A line with an integer number t (1 < t ≤ 20), describing the number of trees in the forest;
• Then, for each tree:
  • A line with the tree location, expressed in an (x, y) integer coordinate (

For each test case, the output contains one line with two integer numbers, separated by a space. The first number indicates the size of the largest connected light zone (in terms of illuminated trees) that can be created, the second number indicates the minimal amount of lanterns needed to illuminate all these trees.