大概做法

观察到答案贡献只有-1,0,1,2。

特判-1,0的情况。

如果存在割点，答案就为1

否则为2.

建图可以离散化，因为只有附近的8个格子才有可能成为割点。

详细做法

戳我

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=25e5+5,M=1e6+5,mod=19260817;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
void mn(int &x,int y){if(x>y)x=y;}
void mx(int &x,int y){if(x<y)x=y;}
int n,m,c;
struct Hash
{
    struct edge{int x,y,next,op,dis;}a[N];int len,last[mod];
    I void ins(int x,int y,int op,int dis)
    {
        if(x<=0||y<=0||x>=n+1||y>=m+1)return ;
        int p=(1ll*(x-1)*m+y)%mod;
        for(int k=last[p];k;k=a[k].next)
            if(a[k].x==x&&a[k].y==y)
            {
                mn(a[k].dis,dis);
                mx(a[k].op,op);
                return ;
            }
        a[++len]=(edge){x,y,last[p],op,dis};last[p]=len;
    }
    I int qry(int x,int y)
    {
        if(x<=0||y<=0||x>=n+1||y>=m+1)return -1;
        int p=(1ll*(x-1)*m+y)%mod;
        if(!last[p])return -1;
        for(int k=last[p];k;k=a[k].next)
            if(a[k].x==x&&a[k].y==y)return k;
        return -1;
    }
    I void clear()
    {
        for(int i=1;i<=len;i++)
        {
            int p=(1ll*(a[i].x-1)*m+a[i].y)%mod;
            last[p]=0;a[i]=(edge){0,0,0,0,0};
        }len=0;
    }
}A;
int dx[N],dy[N];
bool ck()
{
    if(1ll*n*m<=c+1)return 0;
    if(1ll*n*m<=c+2)
    {
        int kx[3],ky[3];kx[0]=ky[0]=0;
        for(int i=1;i<=c;i++)A.ins(dx[i],dy[i],1,0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(A.qry(i,j)==-1)
                    kx[++kx[0]]=i,ky[++ky[0]]=j;
        int d=abs(kx[1]-kx[2])+abs(ky[1]-ky[2]);
        A.clear();
        if(d==1)return 0;
    }
    return 1;
}
const int px[5]={0,-1,0,1,0};
const int py[5]={0,0,-1,0,1};
int f[N];bool vis[N];
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
void merge(int x,int y){f[get(y)]=get(x);}
void dfs(int x,int y,int anc)
{
    int now=A.qry(x,y);
    if(now==-1||vis[now]||A.a[now].op)return ;
    vis[now]=1;merge(anc,now);
    for(int i=1;i<=4;i++)dfs(x+px[i],y+py[i],anc);
}
void dfs(int x,int y,int col,int &flag)
{
    int now=A.qry(x,y);
    if(now==-1||vis[now]||flag)return ;
    vis[now]=1;
    for(int i=1;i<=4;i++)
    {
        int tx=x+px[i],ty=y+py[i],v=A.qry(tx,ty);
        if(v!=-1&&!A.a[v].op)
        {
            if(!col)col=get(v);
            else if(col!=get(v))
            {
                flag=1;
                return ;
            }
        }
    }
    for(int i=1;i<=4;i++)
        dfs(x+px[i],y+py[i],col,flag);
}
bool ck0()
{
    for(int i=1;i<=A.len;i++)f[i]=i,vis[i]=0;
    for(int i=1;i<=A.len;i++)
        if(!A.a[i].op&&!vis[i])dfs(A.a[i].x,A.a[i].y,i);
    for(int i=1;i<=A.len;i++)
        if(A.a[i].op&&!vis[i])
        {
            int flag=0;dfs(A.a[i].x,A.a[i].y,0,flag);
            if(flag)return 0;
        }
    return 1;
}
struct edge{int v,next;}a[N<<2];int len,last[N];
void ins(int u,int v){a[++len]=(edge){v,last[u]};last[u]=len;}
int dfn[N],low[N],cnt,cut,root;
void tarjan(int u)
{
    if(cut)return ;
    dfn[u]=low[u]=++cnt;int siz=0;
    for(int k=last[u],v;k;k=a[k].next)
    {
        if(!dfn[v=a[k].v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);++siz;
            if(dfn[u]<=low[v]&&A.a[u].dis==1)
            {
                if(u!=root||siz>1)
                {
                    cut=1;
                    return ;
                }
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void work()
{
    qr(n),qr(m),qr(c);
    for(int i=1;i<=c;i++)qr(dx[i]),qr(dy[i]);
    if(!ck()){puts("-1");return ;}
    if(n==1)
    {
        sort(dy+1,dy+c+1);
        int ans=1,p=1;
        while(p<=c)
        {
            int loc=p;
            while(loc<=c&&dy[loc+1]==dy[loc]+1)++loc;
            if(dy[p]>1&&dy[p]<m)
            {
                ans=0;break; 
            }
            p=loc+1;
        }
        qw(ans);puts("");
        return ;
    }
    if(m==1)
    {
        sort(dx+1,dx+c+1);
        int ans=1,p=1;
        while(p<=c)
        {
            int loc=p;
            while(loc<=c&&dx[loc+1]==dx[loc]+1)++loc;
            if(dx[p]>1&&dx[p]<n)
            {
                ans=0;break; 
            }
            p=loc+1;
        }
        qw(ans);puts("");
        return ;
    }
    for(int i=1,x,y;i<=c;i++)
    {
        x=dx[i],y=dy[i];
        for(int j=-2;j<=2;j++)
            for(int k=-2;k<=2;k++)
            {
                int d=max(abs(j),abs(k));
                if(!j&&!k)A.ins(x+j,y+k,1,d);
                else A.ins(x+j,y+k,0,d);
            }
    }
    for(int i=1,x,y;i<=A.len;i++)
    {
        if(A.a[i].op)continue;
        x=A.a[i].x,y=A.a[i].y;
        for(int l=1;l<=4;l++)
        {
            int tx=x+px[l],ty=y+py[l];
            int v=A.qry(tx,ty);
            if(~v&&!A.a[v].op)ins(i,v);
        }
    }
    if(!ck0())
    {
        puts("0");
        for(int i=1;i<=A.len;i++)last[i]=0;
        cnt=0;
        A.clear();return ;
    }
    cut=0;
    for(int i=1;i<=A.len;i++)
        if(!dfn[i])
        {
            root=i;tarjan(i);
            if(cut)break;
        }
    cut?puts("1"):puts("2");
    for(int i=1;i<=A.len;i++)
        last[i]=dfn[i]=low[i]=0;
    len=cnt=0;
    A.clear();
}
int main()
{
    file("grid17");
    int T;qr(T);
    while(T--)
    {
        work();
    }
    return 0;
}