The Surveying

As we know, Civil Engineering is the best specialty in the world. To transfer from Computer Science to Civil Engineering, Kuki needs to preview Surveying, the compulsory course.

There are $m$ buildings in this city. Each building can be regarded as a rectangle. The four vertices of the retangle are the Detail Points.

Before starting measurement, Kuki found $n$ positions and would set some of these positions as Control Points. At a Control Point, Kuki can measure all positions within the field of vision. A position can be measured if there is nothing (building or Detail Point) on the segment between this position and a Control Point. In addition, every Control Point should be measured by at least one other Control Points.

Kuki wants to set the mininum number of Control Points to survey all Detail Points. Please help her solve this problem.

Each test contains multiple test cases. The first line contains the number of test cases $T(1 \le T \le 10)$. Description of the test cases follows.

The first line of the input contains two integers $n$ and $m$ $(1\le n \le 20, 1 \le m \le 100)$ indicating the number of stations and the number of buildings.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ $(-2\times 10^6 \le x_i, y_i\le 2\times 10^6)$ indicating that the coordinate of the $i$-th station.

For the following $m$ lines, the $i$-th line contains eight integers $x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},x_{i4},y_{i4}$ $(-2\times 10^6\le x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},x_{i4},y_{i4}\le 2\times 10^6)$ indicating that the four vertices of the $i$-th building. The coordinates are given in counter-clockwise order starting from the top-right corner. It's guaranteed that the boundaries of buildings are parrallel to the coordinate axes. Any two buildings will not intersect or contain. Building boundaries will not overlap.

It's guaranteed that the stations will not be inside or on the boundary of buildings.

For each test case:

If it's impossible to measure all Detail Points, print "No Solution!" in a single line (without quotes).

Otherwise, print one interger in one line indicating the mininum number of Control Points

1
3 3
2 1
2 14
8 14
7 6 3 6 3 3 7 3
7 12 3 12 3 8 7 8
13 9 9 9 9 4 13 4

3

2022“杭电杯”中国大学生算法设计超级联赛（5）