记录编号	407983	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]网格	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	2.200 s
提交时间	2017-05-23 17:02:45	内存使用	194.10 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
const int maxn=100005,maxm=maxn*24;
int n,m,K,ans,X[maxn],Y[maxn],vis[maxn],tim=0;
struct Rabit_tree{int to,next;}e[maxm<<3];
int qx[maxm],qy[maxm],q[maxn],head[maxm],len;
void Set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len;
}
int fir[maxm],low[maxm],cnt;bool ff;
int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
map<LL,int>mp,num;
#define MCP(x,y) (((x)*1ll)<<32|(y))
#define to e[i].to
void Tarjan(int rt,int fa){
	fir[rt]=low[rt]=++cnt;bool iscut=false;int son=0;
	for(int i=head[rt];i;i=e[i].next)if(to^fa)
		if(!fir[to]){
			son++,Tarjan(to,rt),low[rt]=min(low[rt],low[to]);
			if(low[to]>=fir[rt])iscut=true;
		}
		else low[rt]=min(low[rt],fir[to]);
	if(!fa&&son<2)iscut=false;ff|=iscut;
}
void Run(){
	int rt,i,j,s=1,t=1,x,y,tot=0;LL tmp;num.clear();
	while(s<=t){
		rt=q[s++];
		for(i=-2;i<=2;i++)
		for(j=-2;j<=2;j++)if(i||j){
			x=X[rt]+i,y=Y[rt]+j;
			if(x<1||y<1||x>n||y>m)continue;
			tmp=MCP(x,y);
			if(mp.count(tmp)){q[++t]=mp[tmp];if(vis[q[t]]==tim)t--;else vis[q[t]]=tim;}
			else if(!num.count(tmp))qx[++tot]=x,qy[tot]=y,num[tmp]=tot;
		}
	}
	for(i=1;i<=tot;i++)head[i]=fir[i]=0;cnt=0;len=1;
	for(rt=1;rt<=tot;rt++)
		for(i=0;i<4;i++){
			x=qx[rt]+fx[i],y=qy[rt]+fy[i];
			tmp=MCP(x,y);if(num.count(tmp))Set(rt,num[tmp]);
		}
	cnt=0,ff=false;Tarjan(1,0);
	if(cnt<tot){ans=0;return;}
	if(ff)ans=1;
}
int Ans(){
	if(n==1||m==1)ans=1;else ans=2;tim++;
	for(int i=1;i<=K;i++)if(vis[i]^tim){
		q[1]=i,vis[i]=tim,Run();
		if(ans==0)return ans;
	}
	if(n*1ll*m-K==2)ans=-1;return ans;
}
int main(){
	freopen("NOI2016grid.in","r",stdin);freopen("NOI2016grid.out","w",stdout);
	int tt,i;R_int(tt);
	while(tt--){
		R_int(n),R_int(m),R_int(K);
		if(n*1ll*m-K<=1){
			while(K--)R_int(n),R_int(m);
			puts("-1");continue;
		}
		mp.clear();
		for(i=1;i<=K;i++)R_int(X[i]),R_int(Y[i]),mp[MCP(X[i],Y[i])]=i;
		printf("%d\n",Ans());
	}
}