题目描述

跳蚤国王和蛐蛐国王在玩一个游戏。

他们在一个$n$行$m$列的网格上排兵布阵。其中的$c$个格子中$(0 \le c \le nm)$，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。

我们称占据的格子有公共边的两只跳蚤是相邻的。

我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。

现在，蛐蛐国王希望，将某些（$0$个，$1$个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。

例如：我们用图左表示一只跳蚤，用图右表示一只蛐蛐，那么图$1$描述了一个$n = 4, m = 4, c = 2$的情况。

这种情况下蛐蛐国王可以通过将第$2$行第$2$列，和第$3$行第$3$列的两只跳蚤替换为蛐蛐，从而达成他的希望，如图$2$所示。并且，不存在更优的方案，但是可能存在其他替换$2$只跳蚤的方案。

你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成，你还需要最小化被替换的跳蚤的个数。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数$T$，表示数据的组数。保证$1 \le T \le 20$。

接下来依次输入$T$组数据，每组数据的第一行包含三个整数$n,m,c$。保证$1 \le n,m \le 10 ^ 9, 0 \le c \le \min(nm, 10 ^ 5)$。

接下来$c$行，每行包含两个整数$x,y$，表示第$x$行，第$y$列的格子被一个蛐蛐占据$(1 \le x \le n, 1 \le y \le m)$。每一组数据当中，同一个蛐蛐不会被多次描述。

同一行相邻的整数之间由一个空格隔开。

输出格式

对于每一组数据依次输出一行答案。

如果这组数据中，蛐蛐国王的希望不能被达成，输出$-1$。否则，输出被替换的跳蚤的个数的最小值。

题目解析

说实话，我真的很佩服那些在考场上能把这题AC的爷爷们。这种大分类讨论题，居然有人能绕开所有坑。

在同步赛考场上，我乱写了一个做法交上去居然还有56分真感动。（大概是因为特判了$n = 1$或$m = 1$）

言归正传。我们来讨论一下正解。

方便起见，我们把跳蚤格子称为白格，蛐蛐格子称为黑格。

首先，我们可以发现，如果有解，答案总是不会超过$2$的。因为我们总能在网格中找到一个角。

于是我们先判断有没有解。显然，如果网格中白格少于2个，肯定是无解的。如果白格恰好有2个，如果它们是四连通意义下相邻的，也是无解的。否则，一定有解。

如果确定了有解，我们只需要确定答案能否为0或1。

在此之前，我们先特判$n = 1$或$m = 1$的情况。

考虑为0的情况，即白格是不连通的。什么情况下可能不连通呢？我们发现，如果要让白格不连通，一定是一些黑格组成的八连通分量把某些白格围在了内部。由于黑格数量不多，我们可以枚举所有黑格的八连通分量，对其周围的白格DFS一波就好了。但是我们DFS所有白格是$O(nm)$的，考虑优化。

注意到与黑格八连通的白格才有用，其他白格其实是没有意义的。于是我们预处理这些格子，DFS时只走这些格子即可。

再来考虑1的情况，即我们加一个黑格即可把某些白格围住，就像一个环上的缺口。如果我们把所有白格在四连通意义下抽象成一个图，可以发现这样的白格其实是这个图的割点。于是问题转化成了求图是否有割点。求所有白格的割点是$O(nm)$的，考虑优化。

注意到如果有割点，这个割点一定是与某个黑格八连通意义下相邻的。于是所有与某个黑格八连通意义下相邻的白格是要加入图中的。但是如果只搜这些白格，原来不是割点的格子可能就变成割点了。于是与这些白格八连通的白格也要加入图中，但是这些格子不能成为割点。于是再对这些白格DFS一波就好了。

判断白格是否在图中可以用哈希或map实现。如果用哈希，时间复杂度是$O(Tc)$。

这题写起来简直了…… 一言不合就5K。