WA ON #6,#9,#10。

#include <bits/stdc++.h>
using namespace std;
#define _r return*this
#define _o &operator
namespace IO
{
	const int _S = 1 << 21;
	char b[_S], *p1 = b, *p2 = b, pb[_S], *pp = pb;
	void fl()
	{
		fwrite(pb, 1, pp - pb, stdout), pp = pb;
	}
	struct input
	{
		char gc()
		{
			if (p1 == p2)p2 = (p1 = b) + fread(b, 1, _S, stdin);
			return p1 == p2 ? ' ' : *p1++;
		}
		input _o >> (char&c)
		{
			do c = gc();
			while (c == ' ' || c == '\n' || c == '\r' || c == '\t');
			_r;
		}
		template<class T>input _o >> (T&x)
		{
			char c = gc();
			T f = 1;
			for (x = 0; !isdigit(c);)(c == '-' ? f = -1 : 1), c = gc();
			while (isdigit(c))x = (x * 10) + (c ^ 48), c = gc();
			x *= f;
			_r;
		}
		input() {}
	} in;
	struct output
	{
		void pt(char c)
		{
			*pp++ = c;
			if (pp - pb == _S)fl();
		}
		output _o << (char c)
		{
			pt(c);
			_r;
		}
		template<class T>output _o << (T x)
		{
			if (!x)
			{
				pt(48);
				_r;
			}
			if (x < 0)pt('-'), x = -x;
			int s[64], t = 0;
			while (x)s[++t] = x % 10, x /= 10;
			while (t)pt(s[t--] + 48);
			_r;
		}
		output _o << (const char*s)
		{
			int c = 0;
			while (s[c])pt(s[c++]);
			_r;
		}
		output() {}
	} out;
	struct fe
	{
		~fe()
		{
			fl();
		}
	} fls;
}
using IO::in;
using IO::out;
using ll = long long;

#define MOD 590027
#define N 600000

ll n, m;
ll x, y;
bool mp[20][20];

struct answer
{
	ll mn, mx;
	void update(answer B)
	{
		mn = min(mn, B.mn), mx = max(mx, B.mx);
	}
};

ll dp[2][N];
ll total;

ll bit[30];
void init()
{
	for (int i = 1; i <= 25; i++)bit[i] = i << 1;
}

ll sta[2][N], tot[2];
ll pre = 1, cnt;

struct hash_node
{
	ll v, nxt;
} e[N];
ll p[N], pos;
void ins(ll st, ll v)
{
	ll dis = st % MOD;
	for (int i = p[dis]; i; i = e[i].nxt)
		if (sta[cnt][e[i].v] == st)
		{
			dp[cnt][e[i].v] = max(dp[cnt][e[i].v], v);
			return;
		}
	sta[cnt][++tot[cnt]] = st, dp[cnt][tot[cnt]] = v;
	e[++pos] = {tot[cnt], p[dis]}, p[dis] = pos;
}

void PlugDP()
{
	tot[cnt] = 1;
	for (int i = n + 2; i >= 1; i--)
	{
		for (int j = 1; j <= tot[cnt]; j++)sta[cnt][j] <<= 2;
		for (int j = 1; j <= n + 2; j++)
		{
			pos = 0, memset(p, 0, sizeof(p)), swap(pre, cnt), tot[cnt] = 0;
			for (int k = 1; k <= tot[pre]; k++)
			{
				ll st = sta[pre][k], ans = dp[pre][k], d = (st >> bit[j]) & 3, r = (st >> bit[j - 1]) & 3;
				if (!mp[i][j])
				{
					if (!d && !r)ins(st, ans);
				}
				else if (!d && !r)
				{
					if (mp[i - 1][j] && mp[i][j + 1])ins(st + (1 << bit[j - 1]) + (1 << (bit[j] + 1)), ans + 1);
					if (i ^ (n + 2) || j ^ 1)ins(st, ans);
				}
				else if (!d && r)
				{
					if (mp[i - 1][j])ins(st, ans + 1);
					if (mp[i][j + 1])ins(st + r * ((1 << bit[j]) - (1 << bit[j - 1])), ans + 1);
				}
				else if (d && !r)
				{
					if (mp[i][j + 1])ins(st, ans + 1);
					if (mp[i - 1][j])ins(st + d * ((1 << bit[j - 1]) - (1 << bit[j])), ans + 1);
				}
				else if (d == 1 && r == 1)
				{
					ll t = 1;
					for (int l = j + 1; l <= n; l++)
					{
						if (((st >> bit[l]) & 3) == 1)t++;
						else if (((st >> bit[l]) & 3) == 2)t--;
						if (!t)
						{
							ins(st - (1 << bit[j - 1]) - (1 << bit[j]) - (1 << bit[l]), ans + 1);
							break;
						}
					}
				}
				else if (d == 2 && r == 2)
				{
					ll t = 1;
					for (int l = j - 2; l >= 0; l--)
					{
						if (((st >> bit[l]) & 3) == 1)t--;
						else if (((st >> bit[l]) & 3) == 2)t++;
						if (!t)
						{
							ins(st - (1 << (bit[j - 1] + 1)) - (1 << (bit[j] + 1)) + (1 << bit[l]), ans + 1);
							break;
						}
					}
				}
				else if (d == 1 && r == 2)ins(st - (1 << (bit[j - 1] + 1)) - (1 << bit[j]), ans + 1);
				else if (d == 2 && r == 1)
				{
					if (i == 1 && j == n + 2)total = max(total, ans);
				}
			}
		}
	}
}

const pair<ll, ll>d[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool mq[20][20], vis[20][20];
queue<pair<ll, ll>>q;
ll dis[20][20];
void SPFA()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[n][1] = 0, q.push({n, 1}), vis[n][1] = true;
	while (!q.empty())
	{
		x = q.front().first, y = q.front().second, q.pop();
		for (pair<ll, ll>i : d)
		{
			ll nx = x + i.first, ny = y + i.second;
			if (1 <= nx && nx <= n && 1 <= ny && ny <= n && !vis[nx][ny])
				vis[nx][ny] = true, dis[nx][ny] = dis[x][y] + 1, q.push({nx, ny});
		}
	}
}

int main()
{
	in >> n >> m;
	for (int i = 1; i <= n + 2; i++)for (int j = 1; j <= n + 2; j++)mp[i][j] = true;
	for (int i = 2; i <= n + 1; i++)mp[i][2] = mp[2][i] = false;
	while (m--)in >> x >> y, mp[x + 2][y + 2] = false;
	init(), PlugDP(), SPFA(), out << total - dis[1][n] - n * 2 - 5;
}