#include <bits/stdc++.h>
using namespace std;

const int N = 15, M = 110;

int n, m;
int sx, sy, tx, ty;
bool g[N][N];
bool st[N][N];
int ansmax=0;
int ansmin=100;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int t) {
    if (x == tx && y == ty) {  // 到达终点
        ansmax = max(ansmax, t);     // 更新时间
        ansmin = min(ansmin, t);
//        cout<<t;
        return;
    }
    for (int i = 0; i < 4; i++) {  // 尝试四个方向
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && !g[nx][ny] && !st[nx][ny]) {
            st[nx][ny] = true;   // 标记访问
            dfs(nx, ny, t + 1);  // 继续搜索
            st[nx][ny] = false;  // 回溯
        }
    }
}

int main() {
    cin >> n >> m;
    sx = 1, sy = 1;  // 起点坐标
    tx = n, ty = n;  // 终点坐标
    while (m--) {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;  // 标记障碍物
    }
    dfs(sx, sy, 0);
    cout << ansmax - ansmin;
    return 0;
}