program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  MAXIN = 10000;
  INF = MAXINT - 1;

var
  n, m, i, j, x, y, ind, min, ans: integer;
  a: array [1..MAXIN, 1..MAXIN] of integer;
  d, mark: array [1..MAXIN] of integer;
begin
  ans := 0;
  readln(n, m);
  for i := 1 to n do
    for j := 1 to n do
      a[i][j] := 0;

  for i := 1 to m do
  begin
    readln(x, y);
    a[x][y] := 1;
  end;

  for i := 1 to n do
  begin
    mark[i] := 0;
    d[i] := INF;
  end;
  d[1] := 0;

  while (true) do
  begin
    ind := -1;
    min := INF;
    for i := 1 to n do
      if (mark[i] = 0) and (d[i] < min) then
      begin
        ind := i;
        min := d[i];
      end;
    if (ind = -1) then
      break;
    mark[ind] := 1;
    for i := 1 to n do
      if (a[ind][i] <> 0) and (mark[i] = 0) and (d[i] > d[ind] + 1) and (i <> n) then
        d[i] := d[ind] + 1
      else
        if (a[ind][i] <> 0) and (d[i] > d[ind] + 1) and (i = n) then
        begin
          d[i] := d[ind] + 1;
          ans := 1;
        end
        else
        if (i = n) and (a[ind][i] <> 0) and (d[i] = d[ind] + 1) then
          inc(ans);
  end;

  writeln((d[n] - 1) * ans + 2);
  readln;
  readln;
end.