这是 $\text{NOI}$ 的【网格】一题，在洛谷中可以搜到。以下是我的代码，数组和哈希稍微有些玄学，但这不是重点，我没有 $\text{WA}$，也没有 $\text{RE}$，反而 $\text{T}$ 了两个点，得 $92$ 分。

请大佬们帮我条一下（个人马蜂有些像 $\text{AI}$，实际不是 $\text{AI}$）。只要调了，不管调成啥样，就是调成 $0$ 分，我也会关注（当然，有明显恶意性质的除外）。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>
#include <cstring>
#include <chrono>

using namespace std;

#define ll long long
#define pb push_back
#define tup pair<int, int>
#define fi first
#define sec second

constexpr int dx[4] = {1, -1, 0, 0};
constexpr int dy[4] = {0, 0, 1, -1};
constexpr int N = 5e6 + 10;
constexpr int RUN = 32;

char buf[1 << 20], *p1, *p2;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)

inline void read(int &goal) {
	int x = 0, f = 1;
	char ch = gc();
	while (ch < 48 || ch > 57) {
		if (ch == '-') {
			f = -1;
		}
		ch = gc();
	}
	while (ch >= 48 && ch <= 57) {
		x = (x << 1) + (x << 3) + (ch & 15);
		ch = gc();
	}
	goal = x * f;
}

int n, m, c, u, v, idx, col[N], cnt;

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template<typename K, typename V> using hashmap = unordered_map<K, V, custom_hash>;

tup pts[N], cur, tmp;
hashmap<int, hashmap<int, int>> id, edge_map;
queue<tup> q, q_bfs;

struct Edge {
	int to, nxt;
} e[N << 1];

int head[N], rk[N], cut[N], dfn[N], low[N], top, timer;

int exist(int u, int v) {
	int pos = lower_bound(pts + 1, pts + c + 1, (tup) {
		u, v
	}) - pts;
	tup t = pts[pos];
	return (t.fi == u) && (t.sec == v);
}

int out(int x, int y, int u, int d, int l, int r) {
	return (x < u) || (x > d) || (y < l) || (y > r);
}

void add_edge(int u, int v) {
	e[++top] = {
		v, head[u]
	};
	head[u] = top;
}

int check_special() {
	if ((ll)n * m - c <= 1) {
		return 0;
	}
	if ((ll)n * m - c >= 3) {
		return 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!exist(i, j)) {
				for (int k = 0; k < 4; k++) {
					if (out(i + dx[k], j + dy[k], 1, n, 1, m)) {
						continue;
					}
					if (!exist(i + dx[k], j + dy[k])) {
						return 0;
					}
				}
				return 1;
			}
		}
	}
	return 0;
}

void bfs_col(tup st) {
	q_bfs.push(st);
	int u, v, nu, nv;
	while (q_bfs.size()) {
		cur = q_bfs.front();
		q_bfs.pop();
		u = cur.fi;
		v = cur.sec;
		int c = col[id[u][v]];
		for (int k = 0; k < 4; k++) {
			if (!out(nu = u + dx[k], nv = v + dy[k], 1, n, 1, m) &&
			    !exist(nu, nv) &&
				(tmp = {
					nu, nv
				}, id[nu][nv])) {
				if (col[id[tmp.fi][tmp.sec]]) {
					continue;
				}
				col[id[tmp.fi][tmp.sec]] = c;
				q_bfs.push(tmp);
			}
		}
	}
}

int is_connected() {
	while (q.size()) {
		cur = q.front();
		q.pop();
		if (col[id[cur.fi][cur.sec]]) {
			continue;
		}
		col[id[cur.fi][cur.sec]] = ++cnt;
		bfs_col(cur);
	}
	for (int i = 1; i <= c; i++) {
		int u = pts[i].fi, v = pts[i].sec, c = -1;
		for (int di = -2; di <= 2; di++) {
			for (int dj = -2; dj <= 2; dj++) {
				if (out(u + di, v + dj, 1, n, 1, m) ||
				    exist(u + di, v + dj)) {
					continue;
				}
				tmp = {
					u + di, v + dj
				};
				if (c == -1) {
					c = col[id[tmp.fi][tmp.sec]];
				} else if (c != col[id[tmp.fi][tmp.sec]]) {
					return 0;
				}
			}
		}
	}
	return 1;
}

void build_graph(int u, int v) {
	for (int di = -2; di <= 2; di++) {
		for (int dj = -2; dj <= 2; dj++) {
			if (out(u + di, v + dj, 1, n, 1, m) ||
			    exist(u + di, v + dj)) {
				continue;
			}
			tmp = {
				u + di, v + dj
			};
			int x = id[tmp.fi][tmp.sec] ? id[tmp.fi][tmp.sec] :
			        (q.push(tmp), id[tmp.fi][tmp.sec] = ++idx);
			if (!out(u + di + 1, v + dj,
			        max(1, u - 2),
			        min(n, u + 2),
			        max(1, v - 2),
			        min(m, v + 2)) &&
			    !exist(u + di + 1, v + dj)) {
				tmp = {
					u + di + 1, v + dj
				};
				int y = id[tmp.fi][tmp.sec] ? id[tmp.fi][tmp.sec] :
				        (q.push(tmp), id[tmp.fi][tmp.sec] = ++idx);
				if (x > y) {
					if (!edge_map[y][x]) {
						add_edge(x, y);
					}
					add_edge(y, x);
					edge_map[y][x] = 1;
				} else {
					if (!edge_map[x][y]) {
						add_edge(x, y);
					}
					add_edge(y, x);
					edge_map[x][y] = 1;
				}
			}
			if (!out(u + di, v + dj + 1,
			        max(1, u - 2),
			        min(n, u + 2),
			        max(1, v - 2),
			        min(m, v + 2)) &&
			    !exist(u + di, v + dj + 1)) {
				tmp = {
					u + di, v + dj + 1
				};
				int y = id[tmp.fi][tmp.sec] ? id[tmp.fi][tmp.sec] :
				        (q.push(tmp), id[tmp.fi][tmp.sec] = ++idx);
				if (x > y) {
					if (!edge_map[y][x]) {
						add_edge(x, y);
					}
					add_edge(y, x);
					edge_map[y][x] = 1;
				} else {
					if (!edge_map[x][y]) {
						add_edge(x, y);
					}
					add_edge(y, x);
					edge_map[x][y] = 1;
				}
			}
			if (abs(di) <= 1 && abs(dj) <= 1) {
				rk[x] = 1;
			}
		}
	}
}

void tarjan(int u, int fa) {
	cut[u] = 0;
	dfn[u] = low[u] = ++timer;
	int child = 0, v;
	for (int i = head[u]; i; i = e[i].nxt) {
		v = e[i].to;
		if (v == fa) {
			continue;
		}
		if (!dfn[v]) {
			++child;
			tarjan(v, u);
			if (low[v] >= dfn[u] && fa) {
				cut[u] = 1;
			}
			low[u] = min(low[u], low[v]);
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (!fa && child >= 2) {
		cut[u] = 1;
	}
}

void solve() {
	top = idx = timer = cnt = 0;
	memset(head, 0, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(rk, 0, sizeof(rk));
	memset(col, 0, sizeof(col));
	id.clear();
	edge_map.clear();

	read(n), read(m), read(c);
	for (int i = 1; i <= c; i++) {
		read(u), read(v);
		pts[i] = {u, v};
	}

	sort(pts + 1, pts + c + 1);
	pts[c + 1] = {0, 0};

	if (!check_special()) {
		printf("-1\n");
		return;
	}

	for (int i = 1; i <= c; i++) {
		build_graph(pts[i].fi, pts[i].sec);
	}

	if (!is_connected()) {
		printf("0\n");
		return;
	}

	if (n == 1 || m == 1) {
		printf("1\n");
		return;
	}

	for (int i = 1; i <= idx; i++) {
		if (!dfn[i]) {
			tarjan(i, 0);
		}
		if (rk[i] && cut[i]) {
			printf("1\n");
			return;
		}
	}
	printf("2\n");
}

int main() {
	int t;
	read(t);

	while (t--) {
		solve();
	}
	return 0;
}