'''
把棋盘上相邻两个格子看做黑白不同的颜色，增加一块转肯定是连接了
一黑一白两个块，每一个砖块看做一条边，整个问题就是求二分图最大
匹配边的数量，用匈牙利算法求解
'''

from collections import deque
class Bipartite:
    # 传入图中的边信息，所有边起点属于二分图part1, 所有边终点属于二分图part2, 输入数据自行保证没有重边
    # 节点编号从1开始，所有节点编号为1, 2, 3, ..... max_node_num
    def __init__(self, edges, max_node_num):
        self.edges = edges
        self.max_ndoe_num = max_node_num
        self.__match_result = None

    # 获取二分图最大匹配数量, 如果无法进行二分图匹配，返回None, 正常情况返回 (最大匹配数，最大匹配边列表)
    # 节点编号从1开始，所有节点编号为1, 2, 3, ..... max_node_num
    def getMaxMatchNum(self):
        max_node_num = self.max_ndoe_num

        # 构建邻接表
        link = [[] for _ in range(max_node_num + 1)]
        for a, b in self.edges:
            link[a].append(b)

        part1_nodes = set([a for a, _ in self.edges])  # 所有属于part1中的节点
        part2_node2matched = [None] * (max_node_num + 1)  # 记录part2中节点和part1中哪个节点匹配

        cnt = 0
        for start_node in part1_nodes:
            que = deque()
            pre = [None] * (max_node_num + 1)
            visited = [0] * (max_node_num + 1)

            visited[start_node] = 1
            que.append(start_node)

            end_node = None
            find_expand_path = False
            while len(que) > 0:
                cur = que.popleft()

                for next in link[cur]:
                    if visited[next] == 0:
                        visited[next] = 1
                        pre[next] = cur
                        if part2_node2matched[next] is None:
                            # 找到非匹配点，也就是找到了增广路径
                            end_node = next
                            find_expand_path = True
                            break
                        else:
                            pre[part2_node2matched[next]] = next
                            que.append(part2_node2matched[next])

            if find_expand_path:
                flag = True
                if end_node:
                    while pre[end_node] is not None:
                        if flag:
                            part2_node2matched[end_node] = pre[end_node]

                        end_node = pre[end_node]
                        flag = not flag

                cnt += 1

        # 读取匹配的边
        match_edges = []
        for node in range(1, max_node_num + 1):
            if part2_node2matched[node] is not None:
                match_edges.append((part2_node2matched[node], node))

        self.__match_result = cnt, match_edges
        return self.__match_result[0]

n, t = map(int, input().split())
grid = [[0] * (n+1) for _ in range(n+1)]
for i in range(t):
    a, b = map(int, input().split())
    grid[a][b] = 1

edges = []
for i in range(1, n+1):
    for j in range(1, n+1):
        if grid[i][j] == 1:
            continue

        c = None
        idx = (i-1) * n + j
        if n % 2 == 0:
            c = idx&1 if i % 2 == 0 else 1-(idx&1)
        else:
            c = 0 if idx&1 else 1

        for ii, jj in [(i+1, j), (i, j+1)]:
            if ii <= n and jj <= n and grid[ii][jj] == 0:
                if c == 0:
                    edges.append(((i-1)*n+j, (ii-1)*n+jj))
                else:
                    edges.append(((ii-1)*n+jj, (i-1)*n+j))

print(Bipartite(edges, n*n).getMaxMatchNum())