网格 ### 题目描述 跳蚤国王和蛐蛐国王在玩一个游戏。 他们在一个 $n$ 行 $m$ 列的网格上排兵布阵。其中的 $c$ 个格子中 $(0 \leq c \leq n\cdot m)$，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。 我们称占据的格子有公共边的两只跳蚤是相邻的。 我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。 现在，蛐蛐国王希望，将某些（零个，一个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。 如下两图描述了一个 $n=4$，$m=4$，$c=2$ 的情况。   这种情况下蛐蛐国王可以通过将第二行第二列，和第三行第三列的两只跳蚤替换为蛐蛐，从而达成他的希望。并且，不存在更优的方案，但是可能存在其他替换两只跳蚤的方案。 你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成，你还需要最小化被替换的跳蚤的个数。 ### 输入描述 输入包含多组数据。 第一行只有一个整数 $T$，表示数据的组数。 接下来依次输入 $T$ 组数据，每组数据的第一行包含三个整数 $n, m, c$。 接下来 $c$ 行，每行包含两个整数 $x, y$ 表示第 $x$ 行，第 $y$ 列的格子被一个蛐蛐占据。每一组数据当中，同一个蛐蛐不会被多次描述。 其中， $1 \leq n,m \leq 10^9$，$0 \leq c \leq n \times m$，$1 \leq x \leq n, 1 \leq y \leq m$。 ### 输出描述 对于每一组数据依次输出一行答案。 如果这组数据中，蛐蛐国王的希望不能被达成，输出 $-1$。否则，输出被替换的跳蚤的个数的最小值。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 4 4 2 1 1 4 4 2 3 1 1 2 2 2 2 1 1 2 2 1 1 0 ``` >输出 ```txt 2 1 0 -1 ```