题目描述
跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个 n行 m列的网格上排兵布阵。其中的 c个格子中 (0≤c≤nm)，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。
我们称占据的格子有公共边的两只跳蚤是相邻的。
我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。
现在，蛐蛐国王希望，将某些（0 个，1 个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。
例如：我们用图flea表示一只跳蚤，用图cricket表示一只蛐蛐，那么图 1 描述了一个 n=4,m=4,c=2的情况。
这种情况下蛐蛐国王可以通过将第 2 行第 2 列，和第 3 行第 3 列的两只跳蚤替换为蛐蛐，从而达成他的希望，如图 2 所示。并且，不存在更优的方案，但是可能存在其他替换 2 只跳蚤的方案。
输入输出格式
输入格式：
对于每一组数据依次输出一行答案。
如果这组数据中，蛐蛐国王的希望不能被达成，输出。否则，输出被替换的跳蚤的个数的最小值。
输出格式：
输出文件包括1个非负整数
输入输出样例
4 4 4 2 1 1 4 4 2 3 1 1 2 2 2 2 1 1 2 2 1 1 0
2 1 0 -1
说明
第一组数据就是问题描述中的例子。
对于第二组数据，可以将第 2 行第 2 列的一只跳蚤替换为蛐蛐，从而使得存在两只跳蚤不连通，并且不存在更优的方案。
对于第三组数据，最初已经存在两只跳蚤不连通，故不需要再进行替换。
对于第四组数据，由于最多只有一只跳蚤，所以无论如何替换都不能存在两只跳蚤不连通。
对于全部的测试点，保证 1≤T≤20。我们记 ∑c 为某个测试点中，其 T组输入数据的所有 c 的总和。对于所有的测试点，∑c≤10^5。
对于全部的数据，满足 1≤n,m≤109, 0≤c≤nm, 1≤x≤n, 1≤y≤m。
每个测试点的详细数据范围见下表。表中的 n,m,c均是对于单个输入数据（而非测试点）而言的，也就是说同一个测试点下的 T组数据均满足限制条件；而 ∑c是对于单个测试点而言的。为了方便阅读，“测试点”一列被放到了表格的中间而不是左边。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
割点+思路~
答案只有-1,0,1,2四种。
答案为-1：n*m<=1 || (n*m-c==2 && 空下来的两格子联通）
答案为0：空格子已经不连通
答案为1：空格子联通 && 有割点
其余答案为2.
因为n,m<=10^9，所以显然不是所有的格子都能加入边中。而我们发现只有与[与蛐蛐八连通的格子]八连通的格子是有用的，所以我们把这些点加入图中，然后跑tarjan求割点。要注意的是只有当求出的割点中有点是与蛐蛐八连通的时，才能算有割点。
在跑tarjan时，我们再记录一下每个点属于的块，这样在跑完后可以再顺便判断空格子是否联通。
（洛谷卡空间，我的代码是在BZOJ上交的~）
注意：
1.这里的node要重载运算符<，虽然不明白是为什么……
2.判断割点的时候，要加一句特判：当该点是根节点 && 只有一个子节点时，该点不是割点，这个小数据都测不出来啊。
3.用map的时候，判断map里面有没有x一定要用map.count(x)，不能直接用map[x]判断。
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;int t,n,m,c,fi[2400001],ne[2400001],cnt,tot,totnum,bel[100001],kuai[2400001],now,dfn[2400001],low[2400001];
int xx[8]={0,0,1,-1,-1,-1,1,1},yy[8]={1,-1,0,0,-1,1,-1,1};
bool flag,b[2400001],vis[100001];struct node{int x,y;
}a[100001],tmp,q[2400001];map<node,int> id1,id;
vector<int> w0[100001],w[2400001],con[100001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}bool operator < (node u,node v)
{return u.x==v.x ? u.y<v.y:u.x<v.x;
}bool check8(node u)
{node nw;for(int i=0;i<8;i++){nw.x=u.x+xx[i];nw.y=u.y+yy[i];if(id1.count(nw)) return 1;}return 0;
}void dfs1(int u)
{bel[u]=totnum;for(int i=w0[u].size()-1;~i;i--)if(!vis[w0[u][i]]){vis[w0[u][i]]=1;dfs1(w0[u][i]);}
}void dfs(int u,int fa)
{dfn[u]=low[u]=++cnt;int son=0;kuai[u]=now;for(int i=w[u].size()-1;~i;i--){int k=w[u][i];if(k==fa) continue;if(!dfn[k]){son++;dfs(k,u);low[u]=min(low[u],low[k]);if(low[k]>=dfn[u]) b[u]=1;}else low[u]=min(low[u],dfn[k]);}if(son==1 && fa==-1) b[u]=0;
}void cle()
{for(int i=1;i<=c;i++) w0[i].clear(),vis[i]=0;for(int i=1;i<=tot;i++) w[i].clear(),b[i]=0,kuai[i]=0,dfn[i]=0;for(int i=1;i<=totnum;i++) con[i].clear();id1.clear();id.clear();totnum=cnt=now=tot=flag=0;
}bool notconnect()
{for(int i=1;i<=c;i++)for(int j=0;j<8;j++){tmp.x=a[i].x+xx[j];tmp.y=a[i].y+yy[j];if(id1.count(tmp)) w0[i].push_back(id1[tmp]);}for(int i=1;i<=c;i++) if(!vis[i]) vis[i]=1,totnum++,dfs1(i);for(int i=1;i<=c;i++)for(int j=-2;j<=2;j++)for(int k=-2;k<=2;k++){tmp=(node){a[i].x+j,a[i].y+k};if(tmp.x<=0 || tmp.x>n || tmp.y<=0 || tmp.y>m) continue;if(!id1.count(tmp) && !id.count(tmp)){q[++tot]=tmp;id[tmp]=tot;con[bel[i]].push_back(tot);}}for(int i=1;i<=tot;i++)for(int j=0;j<4;j++){tmp=(node){q[i].x+xx[j],q[i].y+yy[j]};if(id.count(tmp)) w[i].push_back(id[tmp]);}for(int i=1;i<=tot;i++) if(!dfn[i]) now++,dfs(i,-1);for(int i=1;i<=tot;i++) if(b[i] && check8(q[i])) flag=1;for(int i=1;i<=totnum;i++){int idnum=-1;for(int j=con[i].size()-1;~j;j--)if(idnum==-1) idnum=kuai[con[i][j]];else if(idnum!=kuai[con[i][j]]) return 1;}return 0;
}int main()
{t=read();while(t--){n=read();m=read();c=read();for(int i=1;i<=c;i++){a[i].x=read();a[i].y=read();id1[a[i]]=i;}if(1ll*n*m<=2 || 1ll*n*m-c<=1){puts("-1");cle();continue;}if(notconnect()){puts("0");cle();continue;}if(1ll*n*m-c==2){if(now==1) puts("-1");else puts("0");cle();continue;}if(n==1 || m==1) flag=1;if(flag) puts("1");else puts("2");cle();}return 0;
}