#include <bits/stdc++.h>
using namespace std;
int n, m;
int dir[405][405], dic[405][405];
int main() {
  memset(dir, 63, sizeof(dir));
  memset(dic, 63, sizeof(dic));
  scanf("%d %d", &n, &m);
  for (int i = 1, x, y; i <= m; i++) {
    scanf("%d %d", &x, &y);
    dir[x][y] = dir[y][x] = 1;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (dir[i][j] == 1061109567) dic[i][j] = 1;
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
        dir[i][j] = min(dir[i][k] + dir[k][j], dir[i][j]);
    }
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int res = dic[i][k] + dic[k][j];
        if (res == dir[i][j]) continue;
        dic[i][j] = min(dic[i][j], res);
      }
    }
  }
  int ans = max(dic[1][n], dir[1][n]);
  if (ans == 1061109567) ans = -1;
  printf("%d\n", ans);
  return 0;
}
