Maximum Bipartite Matching

First, we show that the lengths of the augmenting paths found in successive rounds are strictly increasing.

Suppose the BFS in the current round reaches level $\ell$. Since all unmatched right vertices found by BFS are on the same level, every augmenting path found by DFS in this round has length $\ell$. We need to prove that after augmenting along the set of paths $\{P_i\}$ found in this round, the reoriented directed graph contains no augmenting path of length at most $\ell$.

In fact, if $P$ is a shortest augmenting path relative to $M$ and $P'$ is an augmenting path relative to $M\oplus P$, then $|P'|\ge |P| + 2|P\cap P'|$. This is because $N=(M\oplus P)\oplus P'$ augments relative to $M$ twice. Thus, by an argument analogous to the proof of Berge's lemma, the symmetric difference $M\oplus N=P\oplus P'$ contains at least two vertex-disjoint augmenting paths relative to $M$, namely $P_1$ and $P_2$. By the minimality of $P$,

This shows that $|P'|\ge |P| + 2|P\cap P'|$. Therefore, if after augmenting along $\{P_i\}$ a new augmenting path $P'$ still had the same length, it would have to be disjoint from every one of them, contradicting the maximality of $\{P_i\}$. This contradiction shows that after augmenting along the blocking flow, every new augmenting path is strictly longer.

Finally, we show that the length of an augmenting path increases at most $3|M|^{1/2}$ times.

Let $p=\lfloor|M|^{1/2}\rfloor$. After the first $p$ rounds, the remaining augmenting paths have length at least $|M|^{1/2}$. Let the current matching be $M_p$. As in the preceding case, we can show that the graph $(V,M\oplus M_p)$ contains $|M|-|M_p|$ pairwise vertex-disjoint augmenting paths relative to $M_p$. Each augmenting path uses at least $|M|^{1/2}/2$ matching edges from $M$, so the total number of these paths is at most $2|M|^{1/2}$; that is, $|M|-|M_p|\le 2|M|^{1/2}$. Thus, starting from $M_p$, at most $2|M|^{1/2}$ more augmentations are possible, which also means that the algorithm performs at most $2|M|^{1/2}$ more augmentation rounds. Hence, the total increase in augmenting-path length is at most $3|M|^{1/2}$.

In the optimized algorithm, the augmenting paths in a blocking flow no longer all have the same length, so the preceding complexity proof no longer applies directly. However, by constructing an auxiliary graph for each round, we can still show that the shortest augmenting-path length strictly increases, preserving the worst-case complexity bound.

Let the bipartite graph be $G=(X,Y,E)$ with current matching $M$. Let $W\subseteq Y$ be the set of unmatched right vertices reachable by BFS, and let the shortest augmenting path reaching $y\in W$ have length $d(y)$. Set $d_\text{max} = \max_{y\in W}d(y)$. For each $y\in W$, create a chain starting at $y$ of length $d_\text{max} - d(y)$, marking its new vertices alternately as left and right vertices and its new edges alternately as matching and non-matching edges. Let the resulting graph be $G'=(X',Y',E')$, with matching $M'$ and shortest augmenting-path length $d_\text{max}$. The augmenting paths found in the level graph of $G$ relative to $M$—that is, the shortest augmenting paths reaching the corresponding vertices—are in bijection with the globally shortest augmenting paths in $G'$ relative to $M'$. Therefore, finding a blocking flow and augmenting in the level graph of $G$ is equivalent to doing so in the level graph of $G'$. By the preceding proof, after augmentation, $G'$ has no augmenting path of length $d_\text{max}$. Hence, $G$ has no augmenting path of length $d_\text{min}=\min_{y\in W} d(y)$ either: such a path would extend along the newly added alternating chain and necessarily correspond to an augmenting path in $G'$ of length $d_\text{max}$. Thus, the shortest augmenting-path length is again strictly increasing from one round to the next, and the overall complexity remains $O(|M|^{1/2}|E|)$.

1. The sets $\mathcal E,\mathcal O,\mathcal U$ form a partition of the vertex set, and this partition is independent of the choice of maximum matching $M$.
2. Every maximum matching of $G$ contains a perfect matching among the vertices of $\mathcal U$, and matches every vertex in $\mathcal O$ to a vertex in $\mathcal E$. In other words, the size of a maximum matching of $G$ is $|\mathcal O|+|\mathcal U|/2$.
3. The graph $G$ contains no edge connecting a vertex in $\mathcal E$ to a vertex in $\mathcal E\cup\mathcal U$.

By definition, $\mathcal U$ is disjoint from $\mathcal E\cup\mathcal O$. It remains to prove that $\mathcal E$ and $\mathcal O$ are disjoint. Otherwise, for a vertex $v\in\mathcal E\cap\mathcal O$, there is an alternating path of even length from an unmatched vertex $a$ to $v$, and an alternating path of odd length from an unmatched vertex $b$ to $v$. Since $G$ is bipartite, $a\neq b$, and the edges by which the two paths reach $v$ are respectively a matching edge and a non-matching edge. Connecting the two paths therefore gives an alternating path from $a$ through $v$ to $b$. This is an augmenting path, contradicting the fact that $M$ is a maximum matching. Hence $\mathcal E\cap\mathcal O=\varnothing$.

1. Let $M'$ be a maximum matching different from $M$. Repeating the proof of Berge's lemma shows that $M'\oplus M$ consists only of even-length paths and even cycles. Starting from maximum matching $M$, we can flip the edges in these connected components (swapping matching and non-matching edges) one component at a time to obtain maximum matching $M'$. When an even cycle is flipped, unmatched vertices remain unmatched, and the parity of the lengths of alternating paths starting from them does not change; when an even-length path is flipped, the matching status of its two endpoints is exchanged, but the parity of the path length from either endpoint to any vertex on the path is the same. Therefore, throughout the flipping process, the sets $\mathcal E,\mathcal O,\mathcal U$ remain unchanged. This shows that the decomposition is independent of the choice of maximum matching $M$.
2. If a matching edge occurs on an alternating path starting from an unmatched vertex $v$, its two endpoints necessarily have different parity of distance from $v$ and therefore belong to $\mathcal E$ and $\mathcal O$, respectively; otherwise, both endpoints belong to $\mathcal U$. Thus, every matching edge in a maximum matching is either an $\mathcal E\mathcal O$ edge or a $\mathcal U\mathcal U$ edge. Conversely, an unmatched vertex can be reached by the length-zero alternating path starting from itself, so unmatched vertices occur only in $\mathcal E$; hence every vertex in $\mathcal O$ and $\mathcal U$ is matched. Simple counting shows that the size of a maximum matching is $|\mathcal O|+|\mathcal U|/2$.
3. By definition, any vertex in $\mathcal E$, including $a$, can be reached from an unmatched vertex $v$ by an alternating path of even length; that is, a vertex in $\mathcal E$ is either unmatched or the alternating path $P$ reaching it ends with a matching edge. If the graph $G$ contains an edge connecting $a$ to a vertex in $\mathcal E\cup\mathcal U$, namely $b$, then by the preceding paragraph this edge is necessarily non-matching, and we can extend the alternating path $P$ along it. This puts $b$ in $\mathcal O$, contradicting the first property. Therefore, the graph $G$ contains no edge connecting a vertex in $\mathcal E$ to a vertex in $\mathcal E\cup\mathcal U$.

Let the Dulmage–Mendelsohn decomposition of the bipartite graph $G=(X,Y,E)$ be $V=\mathcal E\cup\mathcal O\cup\mathcal U$. Then a vertex $v\in V$ is critical if and only if $v\in\mathcal O\cup \mathcal U$.

By the properties of the Dulmage–Mendelsohn decomposition, in graph $G$, the vertices in $\mathcal O$ and $\mathcal U$ are matched in every maximum matching. Therefore, every vertex in $\mathcal O\cup \mathcal U$ is critical. It remains to show that no vertex in $\mathcal E$ is critical. If, in a maximum matching $M$, a vertex $a\in\mathcal E$ is critical, there is an even-length alternating path $P$ connecting $a$ to an unmatched vertex $b\in\mathcal E$. Flipping all edges on this path gives a maximum matching $M\oplus P$ in which $a$ is unmatched. Therefore, no vertex in $\mathcal E$ is critical.

Let the Dulmage–Mendelsohn decomposition of the bipartite graph $G=(X,Y,E)$ be $V=\mathcal E\cup\mathcal O\cup\mathcal U$, and let $M$ be one of its maximum matchings. Then an edge $e\in E$ is critical if and only if both endpoints of $e$ are in $\mathcal U$, $e$ is a matching edge in $M$, and relative to $M$ there is no alternating cycle containing $e$.

The endpoints of a critical edge must be critical vertices. By the properties of the Dulmage–Mendelsohn decomposition, matching edges can only be $\mathcal E\mathcal O$ edges or $\mathcal U\mathcal U$ edges. However, no vertex in $\mathcal E$ is critical, so a critical edge must be an $\mathcal U\mathcal U$ edge. Of course, a critical edge must also be a matching edge in $M$. Let $e\in M$ be an $\mathcal U\mathcal U$ edge. It is not critical if and only if there is another maximum matching $M'\neq M$ such that $e\in M\oplus M'$. Repeating the proof of Berge's lemma shows that $M'\oplus M$ consists only of even-length paths and even cycles. One endpoint of each such path is unmatched relative to $M$, so no vertex on a path can be in $\mathcal U$, contradicting the choice of $e$. Hence, $e$ can occur only on an even cycle. Therefore, an $\mathcal U\mathcal U$ edge $e\in M$ is not critical if and only if, relative to $M$, there is an alternating cycle containing $e$. This proves the claim.

In a bipartite graph, the number of vertices in a minimum vertex cover equals the number of edges in a maximum matching.

Let the bipartite graph $G=(X,Y,E)$ have maximum matching $M$. Let $G$'s unmatched left vertices be $U$, and let $Z$ be the set of vertices reachable from them along alternating paths. Then $C=(X\setminus Z)\cup(Y\cap Z)$ is the desired minimum vertex cover.

First, $C$ is a vertex cover. Suppose otherwise: there is an edge $(u,v)\in E$ with $u\in X\cap Z$ and $v\in Y\setminus Z$. Let $P_u$ be an alternating path reaching $u$. If $(u,v)$ is a matching edge, the last edge of $P_u$ is $(v,u)$, contradicting $v\notin Z$; if $(u,v)$ is not a matching edge, we can extend along edge $(u,v)$ the path $P_u$ to obtain an alternating path reaching $v$, again contradicting $v\notin Z$. These contradictions show that every edge has at least one endpoint in $C$, so $C$ is a vertex cover.

It remains to show that $C$ is a minimum vertex cover. To cover all edges of the maximum matching $M$, any vertex cover needs at least $|M|$ vertices. Therefore, it suffices to prove $|C|=|M|$, which makes it a minimum vertex cover. This is equivalent to proving that, besides containing one endpoint of every matching edge, $C$ contains no other vertices; in other words, $C$ contains no unmatched vertex. Suppose otherwise that there is an unmatched vertex $v\in C$. If $v\in X$, then necessarily $v\in U\subseteq Z$, contradicting the construction of $C$; if $v\in Y$, an alternating path reaching $v$ is an augmenting path relative to $M$, which contradicts the fact that $M$ is maximum by Berge's lemma. These contradictions show that no such unmatched vertex exists, and hence $C$ is a minimum vertex cover.

In a graph $G=(V,E)$, a vertex set $C\subseteq V$ is a vertex cover if and only if its complement $V\setminus C$ is an independent set.

A vertex set $C$ is a vertex cover if and only if at least one endpoint of every edge in $E$, say edge $e$, occurs in $C$, if and only if there is no edge in $E$ whose two endpoints both occur in $V\setminus C$, if and only if $V\setminus C$ is an independent set.

In a graph $G=(V,E)$, the sum of the sizes of a minimum vertex cover and a maximum independent set equals the number of vertices.

The sum of the size of a minimum path cover of the DAG $G=(V,E)$ and the size of a maximum matching of the corresponding bipartite graph $G'=(V^\text{in},V^\text{out},E')$ equals the number of vertices.

In the bipartite graph $G'$, each matching $M'$ corresponds to a subgraph of graph $G$, namely $F$, and every vertex in $F$ has indegree and outdegree at most one; that is, $F$ is a collection of pairwise vertex-disjoint paths or cycles in the directed graph $G$. However, $G$ is assumed to be acyclic, so $F$ contains only disjoint paths. Conversely, each such subgraph $F$ yields a corresponding matching. Since the size of matching $M$ equals the number of vertices minus the number of paths in $F$, the minimum path cover problem of $G$ corresponds to the maximum matching problem of $G'$.

Observe that if there are $n$ entries equal to $1$, with no two of these $1$s in the same row or column, a solution necessarily exists; otherwise, no solution exists. The problem is therefore reduced to finding these $n$ entries equal to $1$.

For a particular $1$, selecting this $1$ in the final arrangement means that the row and column of this $1$ are occupied. Thus, construct a bipartite graph with $n$ left vertices and $n$ right vertices. For every element equal to $1$, add an edge between the left vertex corresponding to its row and the right vertex corresponding to its column. We can then solve a bipartite matching problem.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int ct, n, t[100010], x, r[100010], ans, vis[100010], dis[100010];
vector<int> to[100010];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + n + 1, 0);
  fill(dis + 1, dis + n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  for (cin >> ct; ct--;) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        cin >> x;
        if (x) {
          to[i].push_back(j);
        }
      }
    }
    for (; BFS();) {
      for (int i = 1; i <= n; i++) {
        if (!t[i] && DFS(i)) {
          ans++;
        }
      }
    }
    cout << (ans == n ? "Yes" : "No") << '\n';
    for (int i = 1; i <= n; i++) {
      t[i] = r[i] = 0;
      to[i].clear();
    }
    ans = 0;
  }
  return 0;
}

For every unordered pair $(a, b)$, if $a$ can defend $b$, add an edge from the unordered-pair vertex to that lawyer; conversely, add the corresponding edge for $b$ in the reverse direction.

Keeping only the $(a, b)$ pairs that are connected by an edge transforms the problem into maximum matching in a bipartite graph with $m$ left vertices and $n$ right vertices.

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int n, k, u, v, t[200020], r[200020], ans, vis[200020], dis[200020], c;
map<pair<int, int>, int> mp;
vector<int> to[200020];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + n + 1, 0);
  fill(dis + 1, dis + n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

void mxf() {
  for (; BFS();) {
    for (int i = 1; i <= n; i++) {
      if (!t[i] && DFS(i)) {
        ans++;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> u >> v;
    if (mp.find({u, v}) == mp.end()) {
      mp[{u, v}] = mp[{v, u}] = ++c;
    }
    to[v].push_back({mp[{u, v}]});
  }
  mxf();
  cout << (ans == n ? "YES" : "NO") << '\n';
  ans = 0;
  return 0;
}

Consider how the final arrangement is formed:

First cover every coverable cell with a $1 \times 1$ brick. A $1 \times x$ brick can be formed by repeatedly merging $x$ consecutive $1 \times 1$ bricks in the same row, a row merge. Similarly, an $x \times 1$ brick can be formed by repeatedly merging $x$ consecutive $1 \times 1$ bricks in the same column, a column merge.

Clearly, one row merge and one column merge cannot involve the same brick, and the more merges we perform, the fewer bricks remain. Therefore, take row merges as the left vertices and column merges as the right vertices, and use the conflicts described above as edges to construct a bipartite graph. The original problem then becomes a maximum independent set problem in a bipartite graph.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, m, belr[220][220], beld[220][220], dcnt, rcnt, vis[100010], dis[100010],
    t[100010], r[100010], cnt;
char c[220][220];
vector<int> to[100010];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + rcnt + 1, 0);
  fill(dis + 1, dis + rcnt + 1, 0);
  for (int i = 1; i <= rcnt; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

int solve() {
  int rt = 0;
  for (; BFS();) {
    for (int i = 1; i <= rcnt; i++) {
      if (!t[i] && DFS(i)) {
        rt++;
      }
    }
  }
  return rt;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> c[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (c[i][j] == '#') {
        cnt++;
        if (c[i + 1][j] == '#') {
          beld[i][j] = ++dcnt;
        }
        if (c[i][j + 1] == '#') {
          belr[i][j] = ++rcnt;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (c[i][j] == '#') {
        if (c[i - 1][j] == '#' && c[i][j - 1] == '#') {
          to[belr[i][j - 1]].push_back(beld[i - 1][j]);
        }
        if (c[i + 1][j] == '#' && c[i][j + 1] == '#') {
          to[belr[i][j]].push_back(beld[i][j]);
        }
        if (c[i + 1][j] == '#' && c[i][j - 1] == '#') {
          to[belr[i][j - 1]].push_back(beld[i][j]);
        }
        if (c[i - 1][j] == '#' && c[i][j + 1] == '#') {
          to[belr[i][j]].push_back(beld[i - 1][j]);
        }
      }
    }
  }
  cout << cnt - rcnt - dcnt + solve() << '\n';
  return 0;
}

First consider how to solve the problem when no elements have been deleted.

For each multiset, create a new vertex; for each possible answer, create a new vertex. Then, for a multiset corresponding to vertex $l_i$, for each element $a$, add an edge from $l_i$ to $r_a$. This simplified version becomes a maximum bipartite matching problem.

Now add back the deletion operations. We find that this is intractable: deleting one edge may cause the matching to change drastically, and the complexity is unacceptable. Instead, reverse the process: add one edge at a time, then continue forward and augment again. Therefore, this problem can only be solved with the Kuhn algorithm.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  int u, v;
} arr[5050];

int n, m, t[5050], r[5050], d, ot[5050], kil[5050], vis[5050], ans, out[5050];
vector<int> to[5050];

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (r[i] == -1) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i].u;
    if (arr[i].u > m) {
      arr[i].u = m + 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    cin >> arr[i].v;
  }
  cin >> d;
  for (int i = 1; i <= d; i++) {
    cin >> ot[i];
    kil[ot[i]] = 1;
  }
  for (int i = 1; i <= n; i++) {
    if (!kil[i]) {
      to[arr[i].u].push_back(arr[i].v);
    }
  }
  fill(r + 1, r + m + 1, -1);
  for (; ans <= m;) {
    fill(vis, vis + m + 2, 0);
    if (DFS(ans)) {
      ans++;
    } else {
      break;
    }
  }
  out[d] = ans;
  for (int i = d; i > 1; i--) {
    to[arr[ot[i]].u].push_back(arr[ot[i]].v);
    for (; ans <= m;) {
      fill(vis, vis + m + 2, 0);
      if (DFS(ans)) {
        ans++;
      } else {
        break;
      }
    }
    out[i - 1] = ans;
  }
  for (int i = 1; i <= d; i++) {
    cout << out[i] << '\n';
  }
  return 0;
}

Observe that the entire board can be colored so that no two squares of the same color are adjacent; then a knight can attack only a square of the opposite color.

Then we can directly solve a maximum independent set problem in a bipartite graph.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int kD[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
                      {2, 1},   {1, 2},   {-1, 2}, {-2, 1}};

int n, m, ib;
int vis[200020], dis[200020], t[200020], r[200020], ans, u, v, cnta,
    x[220][220], cl[220][220], idx, bel[220][220];
vector<int> to[200020];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return false;
  }
  vis[x] = true;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return true;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return true;
    }
  }
  return false;
}

int BFS() {
  fill(vis + 1, vis + cnta + 1, false);
  fill(dis + 1, dis + cnta + 1, 0);
  for (int i = 1; i <= cnta; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

void din() {
  for (; BFS();) {
    for (int i = 1; i <= cnta; i++) {
      if (!t[i] && DFS(i)) {
        ans++;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    x[u][v] = true;
  }
  cl[1][1] = 1;
  if (!x[1][1]) {
    bel[1][1] = ++idx;
  }
  for (int i = 2; i <= n; i++) {
    cl[1][i] = cl[1][i - 1] ^ 1;
    if (!x[1][i] && cl[1][i]) {
      bel[1][i] = ++idx;
    } else {
      if (!x[1][i]) {
        bel[1][i] = ++ib;
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cl[i][j] = cl[i - 1][j] ^ 1;
      if (!x[i][j] && cl[i][j]) {
        bel[i][j] = ++idx;
      } else {
        if (!x[i][j]) {
          bel[i][j] = ++ib;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!x[i][j]) {
        cnta += cl[i][j];
        for (int k = 0; k < 8; k++) {
          if (i + kD[k][0] > 0 && j + kD[k][1] > 0 &&
              bel[i + kD[k][0]][j + kD[k][1]] &&
              !x[i + kD[k][0]][j + kD[k][1]]) {
            if (cl[i + kD[k][0]][j + kD[k][1]]) {
              to[bel[i + kD[k][0]][j + kD[k][1]]].push_back(bel[i][j]);
            } else {
              to[bel[i][j]].push_back(bel[i + kD[k][0]][j + kD[k][1]]);
            }
          }
        }
      }
    }
  }
  din();
  cout << n * n - m - ans << '\n';
  return 0;
}