考虑将最上中最左的跳蚤孤立，容易发现他的上面和左面没有跳蚤，因此只需要将他的右边和下边替换掉就可以了
答案为-1有两种情况：1.c>=n*m-1;2.c=n*m-2且这两只跳蚤相邻
对于其他情况，将所有跳蚤建图后判断：1.是否有多个连通块；2.是否有割点即可，由于跳蚤数量很多，容易发现只需要选择周围5*5的范围内有蛐蛐的跳蚤建图即可
只选择3*3会有反例（以下q表示蛐蛐，t表示跳蚤）：
ttttt
tttqt
ttttt
tqttt
ttttt
（注意如果c=0那么答案为((n>1)&&(m>1))+1）

1 #include
2 using namespace std;
3 #define N 100005
4 #define mp make_pair
5 #define pii pair
6 struct ji{
7 int nex,to;
8 }edge[N<<5]; 9 queueq;
10 mapa,mat;
11 int t,n,m,k,x[N],y[N],tx[4]={-1,0,0,1},ty[4]={0,-1,1,0};
12 int V,E,head[N<<2],vis[N<<2],dfn[N<<2],low[N<<2],sum[N<<2]; 13 void add(int x,int y){ 14 edge[E].nex=head[x]; 15 edge[E].to=y; 16 head[x]=E++; 17 } 18 void dfs(int k,int fa){ 19 low[k]=dfn[k]=++dfn[0]; 20 for(int i=head[k];i!=-1;i=edge[i].nex) 21 if (edge[i].to!=fa) 22 if (dfn[edge[i].to])low[k]=min(low[k],dfn[edge[i].to]); 23 else{ 24 dfs(edge[i].to,k); 25 low[k]=min(low[k],low[edge[i].to]); 26 if (dfn[k]<=low[edge[i].to])sum[k]++; 27 } 28 } 29 int bfs(int x,int y){ 30 a.clear(); 31 mat[mp(x,y)]=2; 32 q.push(mp(x,y)); 33 for(int i=1;i<=V;i++)vis[i]=dfn[i]=sum[i]=0; 34 V=E=dfn[0]=0; 35 while (!q.empty()){ 36 x=q.front().first; 37 y=q.front().second; 38 q.pop(); 39 for(int dx=-2;dx<3;dx++) 40 for(int dy=-2;dy<3;dy++){ 41 if ((x+dx<1)||(y+dy<1)||(x+dx>n)||(y+dy>m))continue;
42 pii o=mp(x+dx,y+dy);
43 if (mat[o]==1){
44 mat[o]=2;
45 q.push(o);
46 }
47 if (mat[o]==2)continue;
48 if (!a[o]){
49 a[o]=++V;
50 head[V]=-1;
51 for(int dz=0;dz<4;dz++){ 52 int p=a[mp(x+dx+tx[dz],y+dy+ty[dz])]; 53 if (p){ 54 add(V,p); 55 add(p,V); 56 } 57 } 58 } 59 if (a[o]>0)vis[a[o]]|=((-21))return 1;
65 for(int i=2;i<=V;i++) 66 if ((vis[i])&&(sum[i]))return 1; 67 return 2; 68 } 69 int main(){ 70 scanf("%d",&t); 71 memset(head,-1,sizeof(head)); 72 while (t--){ 73 scanf("%d%d%d",&n,&m,&k); 74 if (k>=1LL*n*m-1){
75 for(int i=1;i<=k;i++)scanf("%*d%*d");
76 printf("-1\n");
77 continue;
78 }
79 mat.clear();
80 for(int i=1;i<=k;i++){
81 scanf("%d%d",&x[i],&y[i]);
82 mat[mp(x[i],y[i])]=1;
83 }
84 int ans=2;
85 for(int i=1;i<=k;i++)
86 if (mat[mp(x[i],y[i])]==1)ans=min(ans,bfs(x[i],y[i]));
87 if (((n==1)||(m==1))&&(ans))ans=1;
88 if ((1LL*n*m-2==k)&&(ans))ans=-1;
89 printf("%d\n",ans);
90 }
91 }