const maxn = 500;
      maxq = maxn*maxn;
type tqueue = record
                front, rear, nitem: word;
                itemx, itemy: array[0..maxq-1] of word;
              end;
var n,k,res:word;
    a,b: array[0..maxn+1,0..maxn+1] of boolean;
    queue1,queue2: tqueue;
procedure enter;
var i,j,u,v:word;
begin
  readln(n,k);
  for i:=1 to n do
  for j:=1 to n do
  begin
    a[i,j]:=true;
    b[i,j]:=false;
  end;
  for i:=1 to k do
  begin
    readln(u,v);
    a[u,v]:=false;
  end;
end;
procedure initq1;
begin
  with queue1 do
  begin
    front:=0;
    rear:=1;
    nitem:=0;
  end;
end;
procedure push1(x,y:word);
begin
  with queue1 do
  begin
    front:=(front+1) mod maxq;
    inc(nitem);
    itemx[front]:=x;
    itemy[front]:=y;
  end;
end;
procedure pop1(var x,y:word);
begin
  with queue1 do
  begin
    x:=itemx[rear];
    y:=itemy[rear];
    dec(nitem);
    rear:=(rear+1) mod maxq;
  end;
end;
function empty1:boolean;
begin
  with queue1 do
  empty1:=(nitem=0);
end;
procedure initq2;
begin
  with queue2 do
  begin
    front:=0;
    rear:=1;
    nitem:=0;
  end;
end;
procedure push2(x,y:word);
begin
  with queue2 do
  begin
    front:=(front+1) mod maxq;
    inc(nitem);
    itemx[front]:=x;
    itemy[front]:=y;
  end;
end;
procedure pop2(var x,y:word);
begin
  with queue2 do
  begin
    x:=itemx[rear];
    y:=itemy[rear];
    dec(nitem);
    rear:=(rear+1) mod maxq;
  end;
end;
function empty2:boolean;
begin
  with queue2 do
  empty2:=(nitem=0);
end;
procedure bfs1;
var x,y,i,j:word;
begin
  for i:=1 to n do
  for j:=1 to n do
  b[i,j]:=false;
  j:=queue1.nitem;
  for i:=1 to j do
  begin
    pop1(x,y);
    {writeln('bfs1 ',res,' ',x,' ',y);}
    if (x<n) and (a[x+1,y]) and (not b[x+1,y]) then 
    begin
      push1(x+1,y);
      b[x+1,y]:=true;
    end;
    if (y<n) and (a[x,y+1]) and (not b[x,y+1]) then 
    begin
      push1(x,y+1);
      b[x,y+1]:=true;
    end;
    if (x<n) and (y<n) and (a[x+1,y+1]) and (not b[x+1,y+1]) then 
    begin
      push1(x+1,y+1);
      b[x+1,y+1]:=true;
    end;
  end;
end;
function bfs2:boolean;
var x,y,i,j:word;
    c: array[0..maxn+1,0..maxn+1] of boolean;
begin
  {for i:=1 to n do
  for j:=1 to n do
  c[i,j]:=false;}
  j:=queue2.nitem;
  inc(res);
  for i:=1 to j do
  begin
    pop2(x,y);
    {writeln('bfs2 ',res,' ',x,' ',y);}
    if (x<n) and (a[x+1,y]) and (not c[x+1,y]) then 
    begin
      push2(x+1,y);
      c[x+1,y]:=true;
      if b[x+1,y] then 
      begin
        {writeln(x+1,' ',y);}
        exit(true);
      end;
    end;
    if (y>1) and (a[x,y-1]) and (not c[x,y-1]) then 
    begin
      push2(x,y-1);
      c[x,y-1]:=true;
      if b[x,y-1] then 
      begin
        {writeln(x,' ',y-1);}
        exit(true);
      end;
    end;
    if (x<n) and (y>1) and (a[x+1,y-1]) and (not c[x+1,y-1]) then 
    begin
      push2(x+1,y-1);
      c[x+1,y-1]:=true;
      if b[x+1,y-1] then 
      begin
        {writeln(x+1,' ',y-1);}
        exit(true);
      end;
    end;
  end;
  bfs2:=false;
end;
procedure solve;
begin
  initq1;
  initq2;
  push1(1,1);
  push2(1,n);
  if n=1 then writeln(0)
  else
  begin
    res:=0;
    repeat
      bfs1;
      if bfs2 then 
      begin
        writeln(res);
        exit;
      end;
    until false;
  end;
end;
begin
  enter;
  solve;
end.