跳蚤国王和蛐蛐国王在玩一个游戏。他们在一个 �n 行 �m 列的网格上排兵布阵。其中的 �c 个格子中 0≤�≤�⋅�0≤c≤n⋅m每个格子有一只蛐蛐其余的格子中每个格子有一只跳蚤。我们称占据的格子有公共边的两只跳蚤是相邻的。我们称两只跳蚤是连通的当且仅当这两只跳蚤相邻或存在另一只跳蚤与这两只跳蚤都连通。现在蛐蛐国王希望将某些零个一个或多个跳蚤替换成蛐蛐使得在此之后存在至少两只跳蚤不连通。例如：图

这是一个图论的问题，可以使用并查集来解决。

首先，我们需要将网格中的每个格子编号。将第 i 行第 j 列的格子编号为 (i-1) * m + j。这样，网格中的 � n 行 � m 列的格子就被编号为 1,2,…,n×m。

然后，我们需要定义并查集的操作。首先，我们需要定义一个数组 fa，大小为 n×m+1，并初始化为 [0,1,2,…,n×m]。

接下来，我们需要定义两个操作：

find(x)：返回节点 x 的根节点。
merge(x, y)：将节点 x 和节点 y 所在的集合合并。

在这个问题中，我们需要进行如下操作：

遍历所有的蛐蛐格子，将其合并为一个集合。
统计所有的跳蚤格子的个数 cnt。
遍历所有的跳蚤格子，如果其相邻的格子不在同一个集合中，则将其合并为一个集合，并将 cnt 减一。
判断 cnt 是否大于等于 2。如果是，则输出 cnt 的值；否则，输出 -1。

下面是具体的实现步骤：

定义一个函数 getRoot，用于返回节点 x 的根节点。
定义一个函数 merge，用于将节点 x 和节点 y 所在的集合合并。
定义一个函数 solve，用于解决每组数据。
- 首先，遍历所有的蛐蛐格子，将其合并为一个集合。
- 然后，统计所有的跳蚤格子的个数 cnt。
- 接下来，遍历所有的跳蚤格子，如果其相邻的格子不在同一个集合中，则将其合并为一个集合，并将 cnt 减一。
- 最后，判断 cnt 是否大于等于 2。如果是，则输出 cnt 的值；否则，输出 -1。
读入数据，并依次调用 solve 函数来解决每组数据。

下面是具体的代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000005;
int fa[MAXN];

int getRoot(int x) {
    if (fa[x] == x) return x;
    return fa[x] = getRoot(fa[x]);
}

void merge(int x, int y) {
    int rootX = getRoot(x);
    int rootY = getRoot(y);
    if (rootX != rootY) fa[rootX] = rootY;
}

void solve(int n, int m, int c) {
    for (int i = 1; i <= n * m; i++) {
        fa[i] = i;
    }
    
    for (int i = 1; i <= c; i++) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }
    
    int cnt = n * m - c;
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 || i == n || j == 1 || j == m) {
                int root = getRoot((i - 1) * m + j);
                for (auto dir : dirs) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                        int nroot = getRoot((nx - 1) * m + ny);
                        if (root != nroot) {
                            merge(root, nroot);
                            cnt--;
                        }
                    }
                }
            }
        }
    }
    
    if (cnt >= 2) {
        cout << cnt << endl;
    } else {
        cout << -1 << endl;
    }
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n, m, c;
        cin >> n >> m >> c;
        solve(n, m, c);
    }
    
    return 0;
}

该算法的时间复杂度为 O(nm)