#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, a[N][N], b[N][N];
signed main() {
  scanf("%d%d", &n, &m);
  memset(a, 0x3f, sizeof(a));
  memset(b, 0x3f, sizeof(b));
  for (int i = 1; i <= n; i++) a[i][i] = b[i][i] = 0;
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    a[u][v] = a[v][u] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i][j] != 0x3f3f3f3f || i == j) continue;
      b[i][j] = b[j][i] = 1;
    }
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
        b[i][j] = min(b[i][j], b[i][k] + b[k][j]);
      }
    }
  }
  if (max(a[1][n], b[1][n]) == 0x3f3f3f3f)
    printf("-1\n");
  else
    printf("%d\n", max(a[1][n], b[1][n]));
}
