发现当c=0的时候，我们可以选择把角上的一个点围起来使得答案(le 2)
所以大胆猜想任何时候答案(le 2)
什么时候是-1呢？(cle 2)且这些点相邻。
什么时候是0呢？白点一开始就不连通。
什么时候是1呢？白点中有桥点。
其它时候就是2咯。
于是写个tarjan获得了56的高分。
继续，这个图很多地方都是没用的是，所以尝试优化。
首先桥点肯定在一个黑点的3*3相邻点中。
再加上外围一圈，把黑点的5*5相邻点题出来，做tarjan，就可以找到桥点了吧。
连通性的判断，只判一个点5*5内的点是否连通即可，因为再外面就一定连通了。
注意找到的桥点保留边界上的黑点3*3相邻的 ，其它的可能在这个简略图中是桥点，但是实际上不是。
还要特判n=1或m=1。
用hash表优化寻找坐标。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int N = 2.5e6 + 5;
int mov[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
namespace sub1 {
int n;
int fi[N], to[N * 4], nt[N * 4], tot = 1;
int dfn[N], low[N], dfn0, son[N], cnt[N];
void cl() {
fo(i, 1, n) fi[i] = dfn[i] = low[i] = 0;
tot = 1; dfn0 = 0;
}
void link(int x, int y) {
nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;
nt[++ tot] = fi[y], to[tot] = x, fi[y] = tot;
}
int rt, bl[N], ye[N];
void dg(int x, int la) {
bl[x] = rt;
dfn[x] = low[x] = ++ dfn0;
cnt[x] = son[x] = 0;
for(int i = fi[x]; i; i = nt[i]) if(i != la) {
int y = to[i];
if(!dfn[y]) {
dg(y, i ^ 1);
low[x] = min(low[x], low[y]);
son[x] ++;
if(low[y] >= dfn[x]) cnt[x] ++;
} else low[x] = min(low[x], dfn[y]);
}
if(la == 0) {
ye[x] = son[x] > 1;
} else {
ye[x] = cnt[x] >= 1;
}
}
void work() {
fo(i, 1, n) if(!dfn[i]) {
rt = i;
dg(i, 0);
}
}
}
int T, n, m, c;
int x, y;
ll zh(int x, int y) {
return (ll) (x - 1) * m + y;
}
const int M = 19260817;
struct hash {
int fi[M], d[M], d0;
int nt[N], f[N], tot; ll h[N];
void cl() {
while(d0) fi[d[d0 --]] = 0;
tot = 0;
}
int& operator [] (ll n) {
int y = n % M;
for(int p = fi[y]; p; p = nt[p])
if(h[p] == n) return f[p];
if(!fi[y]) d[++ d0] = y;
nt[++ tot] = fi[y], h[tot] = n; fi[y] = tot;
return f[tot];
}
int find(ll n) {
int y = n % M;
for(int p = fi[y]; p; p = nt[p])
if(h[p] == n) return 1;
return 0;
}
} id, bz;
int b[N][2];
int d[N][2], d0;
int pd(int x, int y) {
return !bz.find(zh(x, y));
}
int ky[N];
void work() {
sub1 :: cl();
id.cl(); bz.cl();
scanf("%d %d %d", &n, &m, &c);
if(c == 0) {
if((ll) n * m <= 2) {
pp("-1
");
} else {
pp("%d
", (n == 1 || m == 1) ? 1 : 2);
}
return;
}
d0 = 0;
fo(i, 1, c) {
scanf("%d %d", &x, &y);
bz[zh(x, y)] = 1;
b[i][0] = x, b[i][1] = y;
}
fo(i, 1, c) {
x = b[i][0], y = b[i][1];
fo(p, -2, 2) fo(q, -2, 2) {
int u = x + p, v = y + q;
if(u > 0 && v > 0 && u <= n && v <= m && pd(u, v)) {
ll z = zh(u, v);
if(!id.find(z)) {
id[z] = ++ d0;
d[d0][0] = u, d[d0][1] = v;
ky[d0] = 0;
}
int t = id[z];
if(abs(p) <= 1 && abs(q) <= 1) ky[t] = 1;
if(u == 1 || u == n || v == 1 || v == m) ky[t] = 1;
}
}
}
sub1 :: n = d0;
fo(i, 1, d0) {
int x = d[i][0], y = d[i][1];
int id1 = id[zh(x, y)];
fo(j, 0, 1) {
int u = x + mov[j][0], v = y + mov[j][1];
if(u > 0 && v > 0 && u <= n && v <= m) {
ll z = zh(u, v);
if(id.find(z)) {
sub1 :: link(id1, id[z]);
}
}
}
}
sub1 :: work();
int ltk = 1;
fo(i, 1, c) {
x = b[i][0], y = b[i][1];
int s = -1;
fo(p, -2, 2) fo(q, -2, 2) {
int u = x + p, v = y + q;
if(u > 0 && v > 0 && u <= n && v <= m && pd(u, v)) {
ll z = zh(u, v);
if(id.find(z)) {
int t = id[z];
if(s == -1) s = sub1 :: bl[t]; else
if(s != sub1 :: bl[t]) ltk = 2;
}
}
}
}
if((ll) n * m - c <= 1) {
pp("-1
"); return;
}
if((ll) n * m - c == 2 && ltk == 1) {
pp("-1
"); return;
}
if(ltk > 1) {
pp("0
"); return;
}
if(n == 1 || m == 1) {
pp("1
"); return;
}
int cntq = 0;
fo(i, 1, d0) if(ky[i] && sub1 :: ye[i])
cntq ++;
pp("%d
", cntq ? 1 : 2);
}
int main() {
scanf("%d", &T);
fo(ii, 1, T) {
work();
}
}