격자

$n \times m$ 크기의 격자가 있다. 격자에는 $c$ $(0 \leq c \leq nm)$개의 1 칸이 있고, 나머지 칸은 모두 0 칸이다.

변을 공유하는 두 칸을 서로 인접한다고 한다. 두 0 칸은 서로 인접하거나, 두 칸 모두와 연결된 세 번째 0 칸이 있으면 서로 연결되어 있다고 한다.

0 칸 중 일부(0개, 1개, 또는 여러 개)를 1 칸으로 바꾸어, 바꾼 뒤에 서로 연결되지 않은 0 칸 두 개가 존재하도록 하려고 한다.

예를 들어 $4 \times 4$ 격자에서 왼쪽 위 모서리와 오른쪽 아래 모서리가 1 칸이고 나머지 칸이 모두 0 칸이라면, 0 칸 두 개를 1 칸으로 바꾸어 목표를 달성할 수 있다. 두 모서리를 잇는 대각선 위의 나머지 두 0 칸을 1 칸으로 바꾸면 된다. 이 경우 2개를 바꾸는 것이 최적이다.

목표를 달성할 수 있는지 판단해야 한다. 달성할 수 있다면 1 칸으로 바꿔야 하는 0 칸의 최소 개수를 출력한다.

입력 파일의 첫 줄에는 테스트 케이스 수 $T$가 주어지고, 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $c$가 주어진다. 다음 $c$개의 줄에는 각각 두 정수 $x$, $y$가 주어지며, 이는 $x$행 $y$열의 칸이 1 칸임을 뜻한다. 같은 1 칸이 한 테스트 케이스에 두 번 이상 나타나지 않는다. 한 줄에서 인접한 두 정수는 공백으로 구분된다.

각 테스트 케이스에 대해 답을 한 줄에 출력한다. 0 칸 두 개를 서로 연결되지 않게 만들 수 없다면 -1을 출력한다. 그렇지 않다면 1 칸으로 바꿔야 하는 0 칸의 최소 개수를 출력한다.

모든 테스트 케이스에 대해 $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$이다. 입력 파일에 있는 모든 테스트 케이스의 $c$ 합을 $\sum c$라고 한다. $\sum c \leq 10^5$이 보장된다.