Purify the Infected Chambers

In an $N \times M$ grid, certain cells are equipped with air purifiers and other cells are infected. At time $0$, the purifiers start working and each hour they purify their adjacent cells in the four cardinal directions (up, down, left, right). Once a cell is purified, it immediately becomes a purifier and can further spread the effect in subsequent hours. Your task is to determine the minimum number of hours required to purify all infected cells. If it is impossible to purify one or more infected cells, output -1.

The grid is indexed from 1 to $N$ for rows and from 1 to $M$ for columns. You are given the positions of purifiers and infected cells. Process each test case independently.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer $T$, the number of test cases.
• For each test case, there are three lines:
  1. The first line contains two integers $N$ and $M$, denoting the number of rows and columns of the grid.
  2. The second line starts with an integer $K$, the number of purifiers, followed by $2K$ integers representing the coordinates of the purifiers (each pair is given as row and column).
  3. The third line starts with an integer $L$, the number of infected cells, followed by $2L$ integers representing the coordinates of the infected cells (each pair is given as row and column).

outputFormat

For each test case, output a single integer on a new line indicating the minimum number of hours required to purify all infected cells. If it is impossible, output -1.## sample

5
4 4
2 1 1 4 4
2 2 2 3 3
3 3
1 1 1
1 3 3
3 3
1 1 1
1 2 2
5 5
1 3 3
1 1 1
3 3
0
1 3 3

2
4
2
4
-1