시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB52266.667%

문제

There is an $n \times m$ grid where $c$ $(0 \leq c \leq nm)$ cells are 1 cells and the rest of the cells are 0 cells.

We say two cells sharing an edge are adjacent. We say two 0 cells are connected if and only if the two 0 cells are adjacent or there exists the third 0 cell that is connected with both cells.

Now we want to replace some (zero, one, or multiple) 0 cells by 1 cells so that after the replacement there exists two zero cells that are not connected with each other.

For example, if there is a $4 \times 4$ grid where the top-left and the bottom-right corners are 1 cells and the rest are 0 cells, then it is optimal to replace 2 0 cells by 1 cells so that there exists two 0 cells that are disconnected from each other: for example, one possible solution is to replace the other two 0 cells on the diagonal connecting the top-left and the bottom-right corners.

You need to check if the goal can be achieved. If the goal can be achieved, you need to output the minimum number of 0 cells that should be made into 1 cells.

입력

Each test input consists of multiple test cases. The first line of the input file consists of an integer $T$ denoting the number of test cases in the input file. $T$ test cases follow.

The first line of each test case consists of three integers $n,m,c$. In the following $c$ lines, each line consists of two integers $x,y$ denoting the cell on the $x$-th row and the $y$-th column is an 1 cell. The same 1 cell won't appear multiple times in the same test case.

Two neighboring integers in a line is separated by a space.

출력

For each test case, output a line denoting the answer.

If in the test case, it is impossible to disconnect two 0 cells, output -1. Otherwise, output the minimum number of 0 cells that should be replaced by 1 cells.

예제 입력 1

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

예제 출력 1

2
1
0
-1

The first test case is the scenario described in the problem description.

For the second test case, it is possible to replace the cell on the second column of the second row by an 1 cell so that there exists two disconnected 0 cells.

For the third test case, since there are two disconnected 0 cells at the beginning, output 0.

For the fourth test case, there is only one 0 cell at the beginning so it is impossible to have two disconnected 0 cells. As a result, the output should be -1.

힌트

For all test cases, $1 \leq n,m \leq 10^9$, $0 \leq c \leq \min(nm,10^5), 1 \leq x \leq n, 1 \leq y \leq m, 1 \leq T \leq 20$.

Let $\sum c$ denote the sum of $c$ among the $T$ test cases in an input file. It is guaranteed that $\sum c \leq 10^5$.

예제 2