Sentry Robots | cho.sh

Problem

We must guard a set of points of interest using sentry robots that cannot move or rotate. A robot can be placed on any grid cell, facing north, south, east, or west. Once placed, a robot guards every point of interest that lies directly in front of it, along the direction it faces, until its line of sight is blocked by an obstacle. Two or more points that lie in the same row or the same column, with no obstacle between them and the robot, can all be guarded by that single robot.

Given a grid of points of interest and obstacles, compute the minimum number of robots needed so that every point of interest is guarded. A point is guarded when some robot faces its direction with no obstacle in between.

In the grid below, # marks an obstacle and * marks a point of interest. The minimum number of robots needed is 2; one valid placement and orientation is shown with arrows. This is only an illustration, not the input or output format.

   Grid             Solution
. . . . . .        . . . . . .
. * # * . .        . * # * . .
. . # . . .        . . # . . .
. * # * . .        . ↑ # ↑ . .

For the next grid, 4 robots are required because of the obstacles.

   Grid             Solution
. * * . .           . → * . .
. * # * .           . ↑ # ↑ .
. # * . .           . # ↓ . .
. . # . .           . . * . .

Input

The first line contains an integer $C$, the number of test cases. Each test case is preceded by a blank line.

Each test case begins with a line containing two integers $Y$ and $X$: the height and the width of the grid. The next line contains an integer $P$, the number of points of interest, followed by $P$ lines, each giving the coordinates $p_y$ and $p_x$ of one point. The next line contains an integer $W$, the number of obstacles, followed by $W$ lines, each giving the coordinates $w_y$ and $w_x$ of one obstacle.

Output

For each test case, print a single line containing the minimum number of robots needed to guard all points of interest.

Constraints:

$1 \le C \le 50$
$1 \le Y, X \le 100$
$0 \le P \le Y \cdot X$
$0 \le W \le Y \cdot X$
$0 \le P + W \le Y \cdot X$
$1 \le p_x, w_x \le X$
$1 \le p_y, w_y \le Y$