…代码码了7k+，250+ sloc。。。前后重构2次才卡常卡过…这题特判多
显然 ans<=2
特判
- n * m - c <= 1, ans=-1
- n * m - c == 2，考虑这两个点的连通性
- min(n,m)==1，直接把区间拿出来，把前缀后缀的连续死节点搞死，中间如果还剩任意then 0 else 1
其他平凡情况
只要判出ans=0 or ans=1就好了。蛐蛐跳蚤打字太难打，下文称为死节点和活节点。
考虑n*m很小
- 建图，dfs一遍，不联通 then 0
- 建图，把活着的节点跑个tarjan，有割点 then 1，此时方案是任意割点
- else 2
考虑n*m很大
- 思路：只考虑被搞死的点周边的点
- 考虑八联通相邻节点，这些点如果不联通 then 0（对应于上文第一条
- 对于每个联通块（指的是选出这些点之后，其他点都活着，却被无视、删除了，剩下的相连节点形成了各个联通块）跑个tarjan，发现会被卡。如图，活表示活节点，死表示死节点，联&蛤表示与死节点相连的活节点：
活活活活活活活活
活联联联活活活活
活联死联活活活活
活联联蛤联联活活
活活活联死联活活
活活活联联联活活
活活活活活活活活- “蛤”这个地方形成了假的割点。
- 怎么处理？
- 答：把与“联”节点相邻的节点也扔进来。记作“连”。
- 那么这张图变成了：
连连连连连活活活
连联联联连活活活
连联死联连连连活
连联联蛤联联连活
连连连联死联连活
活活连联联联连活
活活连连连连连活
（瞎眼...- 跑个tarjan，判断“联”节点里面有没有割点即可。这样蛤节点就不是割点了。
注意，本题在判断什么节点是联节点的时候不能使用map、unordered_map。。。都会t
使用vector+lower_bound可过
#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#ifdef __attribute__
#define fast __attribute__((optimize("O3"), target("no-ieee-fp,arch=amdfam10")))
#define inline fast inline
#else
#define fast
#define inline inline
#endif
#define USE_FREAD_IO
#ifdef USE_FREAD_IO
#define BUF_SIZE 5000010
char buf[BUF_SIZE];
int cur = BUF_SIZE;
FILE *in = stdin;
inline char gnc()
{
if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; }
return buf[cur++];
}
#else
#define gnc getchar
#endif
template<typename T>
inline void gi(T &dx)
{
dx = 0;
int yc = gnc();
//bool nega = false;
while (yc < '0' || yc > '9') { /*nega = (yc == '-' ? true : nega);*/ yc = gnc(); }
while (yc >= '0' && yc <= '9') { dx = (T)(dx * 10 + yc - '0'); yc = gnc(); }
//if (nega) { dx = -dx; }
}
inline void gc(char &x)
{
do x = gnc(); while (!isgraph(x));
}
#if __cplusplus >= 201103l || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103l)
template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
{ gi(a); gi(args...); }
#else
template<typename t1, typename t2> inline void gi(t1 &a, t2 &b) { gi(a); gi(b); }
template<typename t1, typename t2, typename t3> inline void gi(t1 &a, t2 &b, t3 &c) { gi(a); gi(b); gi(c); }
template<typename t1, typename t2, typename t3, typename t4> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d) { gi(a); gi(b); gi(c); gi(d); }
template<typename t1, typename t2, typename t3, typename t4, typename t5> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d, t5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
typedef long long ll;
const int maxn = 6666666;
ll n, m, c;
int T;
struct flea
{
int x, y;
flea() : x(0), y(0) {}
flea(int x, int y) : x(x), y(y) {}
flea &operator+=(const flea &a)
{
x += a.x; y += a.y;
return *this;
}
flea &operator-=(const flea &a)
{
x -= a.x; y -= a.y;
return *this;
}
bool operator<(const flea &a) const
{
return x < a.x || (x == a.x && y < a.y);
}
bool operator==(const flea &a) const
{
return x == a.x && y == a.y;
}
bool operator!=(const flea &a) const
{
return x != a.x || y != a.y;
}
} fs[maxn];
int gw[maxn];
bool ok(const flea &a)
{
return a.x >= 1 && a.x <= n && a.y >= 1 && a.y <= m;
}
flea delta1[] = { // 长度为1四联通
flea(+0,+1), flea(+1,+0), flea(+0,-1), flea(-1,+0)
};
flea delta2[] = { // 长度为1八联通
flea(+0,+1), flea(+1,+1), flea(+1,+0), flea(+1,-1), flea(+0,-1), flea(-1,-1), flea(-1,+0), flea(-1,+1)
};
flea delta3[] = { // 长度为2八联通
//flea(+0,+1), flea(+1,+1), flea(+1,+0), flea(+1,-1), flea(+0,-1), flea(-1,-1), flea(-1,+0), flea(-1,+1),
flea(+0,+2), flea(+1,+2), flea(+2,+2), flea(+2,+1), flea(+2,+0), flea(+2,-1), flea(+2,-2), flea(+1,-2),
flea(+0,-2), flea(-1,-2), flea(-2,-2), flea(-2,-1), flea(-2,+0), flea(-2,+1), flea(-2,+2), flea(-1,+2)
};
int pdist(const flea &a, const flea &b)
{
return abs(a.x - b.x) + abs(a.y - b.y);
}
struct graph
{
int beg[maxn], nxt[maxn], to[maxn];
int e;
void ae(int x, int y)
{
++e;
to[e] = y;
nxt[e] = beg[x];
beg[x] = e;
}
void ae2(int x, int y)
{
ae(x, y);
ae(y, x);
}
} g;
int tme = 0;
int dfn[maxn], low[maxn];
bool vis[maxn];
int gds[maxn], gdc;
int id[maxn];
void havis(int x)
{
if (vis[x]) return;
vis[x] = true;
for (int i = g.beg[x]; i; i = g.nxt[i]) {
int y = g.to[i];
havis(y);
}
}
void dfs(int x, int fa = -1)
{
if (id[x] == 0) return;
dfn[x] = low[x] = ++tme;
int cct = 0; // child cnt
bool good = false;
for (int i = g.beg[x]; i; i = g.nxt[i]) {
int y = g.to[i];
if (y == fa) continue;
if (id[y] == 0) continue;
if (dfn[y]) {
low[x] = min(low[x], dfn[y]);
} else {
++cct;
dfs(y, x);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x]) good = true;
}
}
if ((fa == -1 && cct > 1) || (fa != -1 && good)) gds[++gdc] = x;
}
int calc()
{
if (n * m - c <= 1) { return -1; }
if (n * m - c == 2) {
vector<vector<char> > gg;
gg.resize(n + 1);
for (int i = 1; i <= n; ++i) gg[i].resize(m + 1);
for (int i = 1; i <= c; ++i) gg[fs[i].x][fs[i].y] = 1;
vector<flea> zz;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!gg[i][j]) zz.push_back(flea(i, j));
}
}
if (pdist(zz[0], zz[1]) > 1) return 0;
return -1;
}
if (min(n, m) == 1) {
if (c == 0) return 1;
ll z = n * m;
for (int i = 1; i <= c; ++i) {
gw[i] = fs[i].x * fs[i].y;
}
sort(gw + 1, gw + c + 1);
ll lb = 0, rb = c + 1;
gw[0] = 0, gw[c + 1] = z + 1;
while (lb < rb && gw[lb + 1] == gw[lb] + 1) ++lb;
while (lb < rb && gw[rb - 1] == gw[rb] - 1) --rb;
if (lb + 1 >= rb) return 1;
return 0;
}
// 建立O(c)个重要节点
vector<pair<flea,int> > pol;
for (int i = 1; i <= c; ++i) {
flea t = fs[i];
pol.push_back(make_pair(t, 0));
for (int j = 0; j < sizeof(delta2) / sizeof(flea); ++j) {
t += delta2[j];
if(ok(t)) pol.push_back(make_pair(t, 1));
t -= delta2[j];
}
for (int j = 0; j < sizeof(delta3) / sizeof(flea); ++j) {
t += delta3[j];
if (ok(t)) pol.push_back(make_pair(t, 2));
t -= delta3[j];
}
}
sort(pol.begin(), pol.end());
vector<flea> m;
flea t(-233, -233);
int cc = 0;
for (vector<pair<flea, int> >::iterator i = pol.begin(); i != pol.end(); ++i) {
if (i->first != t) {
t = i->first;
m.push_back(t);
id[++cc] = i->second;
}
}
// 建图
tme = 0;
g.e = 0;
for (int i = 1; i <= cc; ++i) g.beg[i] = 0;
for (vector<flea>::iterator i = m.begin(); i != m.end(); ++i) {
flea t = *i;
for (int j = 0; j < sizeof(delta1) / sizeof(flea); ++j) {
t += delta1[j];
vector<flea>::iterator k = lower_bound(m.begin(), m.end(), t);
if (k != m.end() && *k == t) {
g.ae(i - m.begin() + 1, k - m.begin() + 1);
}
t -= delta1[j];
}
}
for (int i = 1; i <= cc; ++i) {
dfn[i] = low[i] = 0;
vis[i] = false;
}
gdc = 0;
for (int i = 1; i <= cc; ++i) {
if (id[i] && !dfn[i]) {
if (vis[i]) return 0;
havis(i);
dfs(i);
}
}
//if (tme < cc) return 0;
for (int i = 1; i <= gdc; ++i) {
if (id[gds[i]] == 1) return 1;
}
return 2;
}
int main()
{
gi(T);
for (int T_ = 1; T_ <= T; ++T_) {
gi(n, m, c);
for (int i = 1; i <= c; ++i) {
gi(fs[i].x, fs[i].y);
}
printf("%d\n", calc());
}
return 0;
}