记录编号	395587	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]网格	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.008 s
提交时间	2017-04-16 19:59:32	内存使用	300.69 MiB

#pragma comment(linker, "/STACK:102400000,102400000") 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
#define for_next() \
for (int fx=-2;fx<=2;fx++)\
for (int fy=-2;fy<=2;fy++)\
if (fx||fy)
const int N=3e6+10,SIZE=1e7+10;
const int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1};
struct hash_table{
	pr key[SIZE];int val[SIZE];
	int& operator [] (const pr &x){
		int ans=0;
		for (int i=x.first;i;i/=13) ans=ans*23+i%13;
		for (int i=x.second;i;i/=13) ans=ans*23+i%13;
		ans%=SIZE;
		if (ans<0) ans+=SIZE;
		while (key[ans]!=x&&val[ans]) ans==SIZE?ans=0:ans++;
		key[ans]=x;
		return val[ans];
	}
}M;
//map<pr,int> M;
int T,n,m,size,c,x[N],y[N],next[N*4],w[N*4],head[N],cnt;
bool ok[N];
void add(int f,int t){
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
pr q[N];
int ID(int x,int y){
	if (x<=0||y<=0||x>n||y>m) return 0;
	return M[pr(x,y)];
}
bool no(int x,int y){
	if (x<=0||y<=0||x>n||y>m) return 0;
	return !M[pr(x,y)];
}
int vis[N],C;
void visit(int v){
	if (vis[v]) return;
	vis[v]=C;
	for (int i=head[v];i;i=next[i]) visit(w[i]);
}
int dfn[N],low[N];bool cut;
void tarjan(int x,int fa){
	static int cnt=0;
	int child=0;
	dfn[x]=low[x]=++cnt;
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (!dfn[v]){
			tarjan(v,x);
			low[x]=min(low[x],low[v]);
			child++;
			if (ok[x]&&fa&&low[v]>=dfn[x]) cut=1;
		}
		else low[x]=min(low[x],dfn[v]);
	}
	if (ok[x]&&!fa&&child>1) cut=1;
}
void init(){
	while (cnt) next[cnt--]=0;
	for (int i=size;i;i--){
		head[i]=dfn[i]=low[i]=vis[i]=ok[i]=0;
		M[q[i]]=0;
	}
	for (int i=c;i;i--) M[pr(x[i],y[i])]=0;
	size=cut=0;
	//M.clear();
}
void solve(int T){
	init();
	scanf("%d%d%d",&n,&m,&c);
	for (int i=1;i<=c;i++){
		scanf("%d%d",&x[i],&y[i]);
		M[pr(x[i],y[i])]=-1;
	}
	for (int i=1;i<=c;i++)
	for_next(){
		int a=x[i]+fx,b=y[i]+fy;
		if (no(a,b)){
			q[++size]=pr(a,b);
			M[q[size]]=size;
		}
	}
	if (c>=(ll)n*m-1) return (void)puts("-1");
	for (int i=1;i<=size;i++){
		int x=q[i].first,y=q[i].second;
		if (x==1||x==n||y==1||y==m) ok[i]=1;
		for (int k=0;k<4;k++){
			int a=x+fx[k],b=y+fy[k],v=ID(a,b);
			if (v>0) add(i,v);
		}
	}
	for (int i=1;i<=size;i++)
		if (!vis[i]) C=i,visit(i);
	for (int i=1;i<=c;i++){
		int S=0;
		for_next(){
			int a=x[i]+fx,b=y[i]+fy,v=ID(a,b);
			if (v>0){
				if (abs(fx)<=1&&abs(fy)<=1) ok[v]=1;
				if (S&&S!=vis[v]) return (void)puts("0");
				S=vis[v];
			}
		}
	}
	if (c==(ll)n*m-2) return (void)puts("-1");
	if (n==1||m==1) return (void)puts("1");
	for (int i=1;i<=size;i++)
		if (!dfn[i]) tarjan(i,0);
	if (cut) return (void)puts("1");
	puts("2");
}
int main()
{
	freopen("NOI2016grid.in","r",stdin);
	freopen("NOI2016grid.out","w",stdout);
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	scanf("%d",&T);
	for (int i=1;i<=T;i++) solve(i);
	return 0;
}