rt,link.
code:

#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int n, m;
bool ob[15][15], vis[105];
queue<pair<int, int> > q;
vector<int> g[105];
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int shortest() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (ob[i][j])
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (ob[x][y])
                        g[(i - 1) * n + j].emplace_back((x - 1) * n + y);
                }
    q.push(make_pair(1, 0));
    vis[1] = true;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i: g[x])
            if (!vis[i]) {
                if (i == n * n)
                    return y + 1;
                q.push(make_pair(i, y + 1));
                vis[i] = true;
            }
    }
    return 0;
}
inline int get(int ori, int pos) {
    return pos > 0 ? (ori >> (pos - 1) * 2) & 3 : 0;
}
inline int set(int ori, int pos, int to) {
    return ((((ori >> pos * 2) << 2) ^ to) << (pos - 1) * 2) ^ (ori & ((1 << (pos - 1) * 2) - 1));
}
map<int, int> dp[2];
stack<int> st;
int p[15];
int find_pair(int sta, int pos) {
    for (int i = 1; i <= n + 1; i++)
        if (get(sta, i) == 1)
            st.push(i);
        else if (get(sta, i) == 2) {
            p[st.top()] = i;
            p[i] = st.top();
            st.pop();
        }
    return p[pos];
}
int longest() {
    int cnt = 0;
    dp[0].clear();
    dp[1].clear();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cnt++;
            if (i == 1 && j == 1) {
                dp[cnt & 1][set(0, 1, 3)] = 1;
                dp[cnt & 1][set(0, 2, 3)] = 1;
            } else if (i == n && j == n) {
                int ans = 0;
                for (auto it: dp[!(cnt & 1)])
                	if ((bool)get(it.first, n) + (bool)get(it.first, n + 1) == 1)
                        ans = max(ans, it.second);
                return ans;
            } else if (!ob[i][j])
                for (auto it: dp[!(cnt & 1)])
                    dp[cnt & 1][it.first] = it.second;
            else
                for (auto it: dp[!(cnt & 1)]) {
                    int status = it.first, dis = it.second;
                    if (j == 1)
                        status = (status & ((1 << n * 2) - 1)) << 2;
                    int l = get(status, j), u = get(status, j + 1);
                    if (!l && !u) {
                        int cur = status;
                        dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis);
                        cur = set(set(status, j, 1), j + 1, 2);
                        if (ob[i][j + 1] && ob[i + 1][j])
                            dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (!l) {
                        int cur = status;
                        if (ob[i][j + 1])
                            dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                        cur = set(set(status, j, u), j + 1, 0);
                        if (ob[i + 1][j])
                            dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (!u) {
                        int cur = status;
                        if (ob[i + 1][j])
                            dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                        cur = set(set(status, j, 0), j + 1, l);
                        if (ob[i][j + 1])
                            dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (l == 1 && u == 1) {
                        int cur = set(set(status, j, 0), j + 1, 0), p = 0;
                        for (int k = 1; k <= n + 1; k++) {
                            if (get(cur, k) == 1)
                                p++;
                            if (get(cur, k) == 2)
                                p--;
                            if (p < 0 && k > j + 1) {
                                cur = set(cur, k, 1);
                                break;
                            }
                        }
                        dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (l == 2 && u == 2) {
                        int cur = set(set(status, j, 0), j + 1, 0), p = 0;
                        for (int k = n + 1; k >= 1; k--) {
                            if (get(cur, k) == 1)
                                p++;
                            if (get(cur, k) == 2)
                                p--;
                            if (p > 0 && k < j) {
                                cur = set(cur, k, 2);
                                break;
                            }
                        }
                        dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (l == 2 && u == 1) {
                        int cur = set(set(status, j, 0), j + 1, 0);
                        dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (l == 2 && u == 3) {
                        int cur = set(set(set(status, j, 0), j + 1, 0), find_pair(status, j), 3);
                        dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    } else if (l == 3 && u == 1) {
                        int cur = set(set(set(status, j, 0), j + 1, 0), find_pair(status, j + 1), 3);
                        dp[cnt & 1][cur] = max(dp[cnt & 1][cur], dis + 1);
                    }
                }
            dp[!(cnt & 1)].clear();
        }
    return 0;
}
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ob[i][j] = true;
    while (m--) {
        int x, y;
        scanf("%lld%lld", &x, &y);
        ob[x][n - y + 1] = false;
    }
    printf("%lld", longest() - shortest());
    return 0;
}