P1173 [NOI2016] Grid

The Flea King and the Cricket King are playing a game. They deploy pieces on an $n$-row, $m$-column grid. Among the $c$ cells ($0 \leq c \leq n \cdot m$), each such cell contains a cricket, and each remaining cell contains a flea. Two fleas are called adjacent if their occupied cells share a side. Two fleas are called connected if and only if they are adjacent, or there exists a sequence of fleas starting from one and ending at the other such that consecutive fleas in the sequence are adjacent. Now, the Cricket King wants to replace some fleas (zero, one, or more) with crickets so that afterwards there exist at least two fleas that are not connected. For example: Figure $1$ describes a case with $n=4$, $m=4$, $c=2$.  In this case, the Cricket King can replace the fleas at row $2$, column $2$ and row $3$, column $3$ with crickets to achieve his goal, as shown in the right picture. Moreover, no better plan exists, although there may be other plans that also replace two fleas. You must first determine whether the Cricket King's goal can be achieved. If it can, you must also minimize the number of fleas replaced.

Each input file contains multiple test cases. The first line contains a single integer $T$, the number of test cases. For each of the next $T$ test cases, the first line contains three integers $n, m, c$. Then $c$ lines follow. Each line contains two integers $x, y$ indicating that the cell in row $x$, column $y$ is occupied by a cricket. Within each test case, no cricket cell is listed more than once.

For each test case, output one line. If the Cricket King's goal cannot be achieved for this test case, output $-1$. Otherwise, output the minimum number of fleas that must be replaced.

### Sample explanation - The first test case is the example in the statement. - For the second test case, replacing the flea at row $2$, column $2$ makes two fleas not connected, and no better plan exists. - For the third test case, there already exist two fleas that are not connected initially, so no replacements are needed. - For the fourth test case, since there is at most one flea, no matter how you replace, there cannot exist two fleas that are not connected. ### Constraints For all test points, it is guaranteed that $1 \leq T \leq 20$. Let $\sum c$ denote, within one test point, the sum of $c$ over its $T$ test cases. For all test points, $\sum c \leq 10^5$. For all data, $1 \leq n, m \leq 10^9$, $0 \leq c \leq n \times m$, $1 \leq x \leq n$, $1 \leq y \leq m$. The detailed constraints for each test point are shown in the table below. In the table, $n, m, c$ refer to a single test case (not a test point), i.e., all $T$ test cases within the same test point meet the listed limits; and $\sum c$ is for a single test point. For readability, the “Test Point” column is placed in the middle rather than on the left. | $n,m$ | Test Point | $c$ | | :----------: | :----------: | :----------: | | $n\times m\leq 4$ | $1$ | $c\leq n\times m$ | | $n\times m\leq 8$ | $2$ | ^ | | $n\times m\leq 15$ | $3$ | ^ | | $n\times m\leq 30$ | $4$| ^ | | $n\times m\leq 100$ | $5$ | ^ | | $n\times m\leq 300$ | $6$ | ^ | | $n\times m\leq 10^3$ | $7$ | ^ | | $n\times m\leq 2\times 10^4$ | $8$ | $c\leq 5$ | | ^ | $9$ | $c\leq 15$ | | ^ | $10$ | $c\leq 30$ | | $n,m\leq 2\times 10^4,n\times m\leq2\times 10^4$ | $11$ | $\sum c\leq 2\times 10^4$ | | $n,m\leq 2\times 10^4,n\times m\leq10^5$ | $12$ | ^ | | $n,m\leq 2\times 10^4,n\times m\leq3\times 10^5$ | $13$ | ^ | | $n,m\leq 2\times 10^4,n\times m\leq10^6$ | $14$ | ^ | | $n,m\leq 2\times 10^4,n\times m\leq 10^9$ | $15$ | ^ | | $n,m\leq 10^5$ | $16$ | $\sum c\leq 10^5$ | | $n,m\leq 10^9$ | $17$ | $c=0$ | | ^ | $18$ | $c\leq 1$ | | ^ | $19$ | $c\leq 2$ | | ^ | $20$ | $c\leq 3$ | | ^ | $21$ | $c\leq 10$ | | ^ | $22$ | $c\leq 30$ | | ^ | $23$ | $c\leq 300$ | | ^ | $24$ | $\sum c\leq 2 \times 10^4$ | | ^ | $25$ | $\sum c\leq 10^5$ | Translated by ChatGPT 5