求救！！Wax8

#include<bits/stdc++.h>
#define INF 0x7fffffff

using namespace std;

int N, n, m, k, ans, mark[40005];
int head[40005], ne[1000005], to[1000005], cap[1000005], cnt = 1;
int cur[40005], dis[40004];

inline int Num(int x, int y) {
    return x*n-n+y;
}

inline void add(int x, int y) {
    if(mark[y]) return;
    int z;
    if(x == 0 || y == N) z = 1;
    else z = INF;
    ne[++cnt] = head[x], head[x] = cnt, to[cnt] = y, cap[cnt] = z;
    ne[++cnt] = head[y], head[y] = cnt, to[cnt] = x;
}

int BFS() {
    queue<int> que;
    memset(dis, 0, sizeof(dis));
    for(int i = 0; i <= N; ++i) cur[i] = head[i];
//  memcpy(cur, head, sizeof(head));
    dis[0] = 1, que.push(0);
    while(!que.empty()) {
        int x = que.front(); que.pop();
        for(int i = head[x]; i; i = ne[i])
            if(!dis[to[i]] && cap[i]) {
                dis[to[i]] = dis[x] + 1;
                que.push(to[i]);
            }
    }
    return dis[N];
}

int DFS(int s, int t) {
    if(s == t) return 1;
    for(int &i = cur[s]; i; i = ne[i])
        if(dis[to[i]] == dis[s] + 1 && cap[i])
            if(DFS(to[i], t)) {
                --cap[i], ++cap[i^1];
                return 1;
            }
    return 0;
}

int main() {
    int ra, rb;
    ios::sync_with_stdio(0);
//  freopen("in", "r", stdin);
//  freopen("out", "w", stdout);
    cin >> n >> m;
    N = n*n+1, ans = n*n-m;
    for(int i = 1; i <= m; ++i) {
        cin >> ra >> rb;
        mark[Num(ra, rb)] = 1;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) {
            int nu = Num(i, j);
            if(mark[nu]) continue;
            if(!(nu&1)) add(nu, N);
            else add(0, nu);
            if(i > 2) {
                if(j > 1) add(nu, Num(i-2, j-1));
                if(j < n) add(nu, Num(i-2, j+1));
            }
            if(i < n-1) {
                if(j > 1) add(nu, Num(i+2, j-1));
                if(j < n) add(nu, Num(i+2, j+1));
            }
            if(j > 2) {
                if(i > 1) add(nu, Num(i-1, j-2));
                if(i < n) add(nu, Num(i+1, j-2));
            }
            if(j < n-1) {
                if(i > 1) add(nu, Num(i-1, j+2));
                if(i < n) add(nu, Num(i+1, j+2));
            }
        }
    while(BFS()) while(DFS(0, N)) --ans; // Dinic
    cout << ans << endl;
    return 0;
}