记录编号	425729	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]网格	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	7.516 s
提交时间	2017-07-15 19:12:50	内存使用	173.89 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

const int MAXK = 100010;
const int MAXN = MAXK * 24;
const int HSIZE = 9999991;

namespace hash {
	int head[HSIZE], next[MAXN], coord[MAXN][2], id;
	inline void init() {
		id = 1; memset(head, 0, sizeof(head));
	}
	inline int find(int x, int y) {
		int i, hv = ((x * 3131 + y) & 0x7fffffff) % HSIZE;
		i = head[hv];
		while(i) {
			if(coord[i][0] == x && coord[i][1] == y) return i;
			i = next[i];
		}
		return 0;
	}
	inline bool ins(int x, int y) {
		if(!find(x, y)) {
			int hv = ((x * 3131 + y) & 0x7fffffff) % HSIZE;

			next[id] = head[hv]; 
			coord[id][0] = x; coord[id][1] = y;
			head[hv] = id++;
			return 1;
		}
		return 0;
	}
}

int MX, MY, K;

namespace conn {
	int head[MAXK], next[4*MAXK], tail[4*MAXK], id;
	inline void link(int u, int v) {
		next[id] = head[u]; tail[id] = v; head[u] = id++;
	}
	inline void init() {
		id = 1; memset(head, 0, sizeof(head));
	}

	int ccid[MAXK], ncc;
	void dfs(int u) {
		int i, v;
		ccid[u] = ncc;
		for(i=head[u];i;i=next[i]) {
			v = tail[i];
			if(!ccid[v]) dfs(v);
		}
	}
	void work() {
		int u;
		ncc = 0; memset(ccid, 0, sizeof(ccid));
		for(u=1;u<=K;u++) if(!ccid[u]) ncc++, dfs(u);
	}
}

namespace graph {
	int head[MAXN], next[4*MAXN], tail[4*MAXN], id;
	vector<int> node[MAXK];

	inline void link(int u, int v) {
		next[id] = head[u]; tail[id] = v; head[u] = id++;
	}
	inline void init() {
		id = 1; memset(head, 0, sizeof(head));
	}
	int dfn[MAXN], clock = 1;
	bool iscut[MAXN], hvcut;

	int ccid[MAXN], ncc;
	int dfs(int u, int fa) {
		int i, v, lowv;
		int lowu = dfn[u] = clock++, child = 0;
		ccid[u] = ncc;

		iscut[u] = 0;
		for(i=head[u];i;i=next[i]) {
			v = tail[i];
			if(!dfn[v]) {
				child++;
				lowv = dfs(v, u);
				lowu = min(lowu, lowv);
				if(lowv >= dfn[u]) iscut[u] = 1;
			}
			else if(dfn[v] < dfn[u] && v != fa) lowu = min(lowu, dfn[v]);
		}
		if(!fa && child <= 1) iscut[u] = 0;
		if(iscut[u]) {
			int x = hash::coord[u+K][0], y = hash::coord[u+K][1], dx, dy;
			
			bool ok = 0;
			for(dx=-1;dx<=1;dx++) for(dy=-1;dy<=1;dy++) if(dx || dy) {
				i = hash::find(x+dx, y+dy);
				if(i && i <= K) {
					ok = 1; break;
				}
			}
			if(ok) hvcut = 1;
		}
		return lowu;
	}

	inline int solve() {
		int i, t, u, x, y, dx, dy;
		hvcut = 0; clock = 1; ncc = 0;
		memset(dfn, 0, sizeof(dfn));
		for(u=K+1;u<hash::id;u++) if(!dfn[u - K]) ++ncc, dfs(u - K, 0);
		for(i=1;i<=conn::ncc;i++) {
			int Num = 0;
			for(t=0;t<node[i].size();t++) {
				x = hash::coord[node[i][t]][0];
				y = hash::coord[node[i][t]][1];
				for(dx=-1;dx<=1;dx++) for(dy=-1;dy<=1;dy++) if(dx || dy) {
					if((u = hash::find(x+dx, y+dy)) > K) {
						if(!Num) Num = ccid[u - K];
						else if(Num != ccid[u - K]) return 0;
					}
				}
			}
		}
		return hvcut ? 1 : ((MX == 1 || MY == 1) ? 1 : 2);
	}
}

const int fx[4] = {0, 1, 0, -1};
const int fy[4] = {1, 0, -1, 0};

inline void work() {
	int i, x, y, dx, dy, dir;
	hash::init();
	graph::init();
	conn::init();
	scanf("%d%d%d", &MX, &MY, &K);
	for(i=1;i<=K;i++) {
		scanf("%d%d", &x, &y); hash::ins(x, y);
	}

	if((ll)MX * MY - K <= 1) printf("-1\n");
	else if(K == 0) {
		if((ll)MX * MY - K == 2) printf("-1\n");
		else printf("%d\n", (MX == 1 || MY == 1) ? 1 : 2);
	}
	else {
		//link 0
		for(i=1;i<=K;i++) for(dir=0;dir<4;dir++) {
			x = hash::coord[i][0] + fx[dir]; y = hash::coord[i][1] + fy[dir];
			if(x = hash::find(x, y)) conn::link(i, x);
		}
		//get 0
		conn::work();
		for(i=1;i<=conn::ncc;i++) graph::node[i].clear();
		for(i=1;i<=K;i++) graph::node[conn::ccid[i]].push_back(i);
		//link
		for(i=1;i<=K;i++) for(dx=-2;dx<=2;dx++) for(dy=-2;dy<=2;dy++) if(dx || dy) {
			x = hash::coord[i][0] + dx; y = hash::coord[i][1] + dy;
			if(x >= 1 && y >= 1 && x <= MX && y <= MY) hash::ins(x, y);
		}
		//link side
		for(i=K+1;i<hash::id;i++) for(dir=0;dir<4;dir++) {
			x = hash::coord[i][0] + fx[dir]; y = hash::coord[i][1] + fy[dir];
			if((x = hash::find(x, y)) > K) graph::link(i - K, x - K);
		}

		int tmp = graph::solve();
		if((ll)MX * MY - K == 2 && tmp) tmp = -1;
		
		printf("%d\n", tmp);
	}
}

int main() {
    int size = 128 << 20;
    char *p = (char*)malloc(size) + size;  
    __asm__("movl %0, %%esp\n" :: "r"(p));
	
	freopen("NOI2016grid.in", "rt", stdin);
	freopen("NOI2016grid.out", "wt", stdout);

	int T; scanf("%d", &T);
	while(T--) work();
}