#include <bits/stdc++.h>
using namespace std;
long long a[405][405];
long long b[405][405];
int n, m;
int main() {
  cin >> n >> m;
  int i, j, k;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) a[i][j] = b[i][j] = 1 << 30;
  for (i = 1; i <= n; i++) a[i][i] = b[i][i] = 0;
  for (i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    a[x][y] = a[y][x] = 1;
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if (i != j && a[i][j] == 1 << 30) b[i][j] = 1;
    }
  }
  for (k = 1; k <= n; k++) {
    for (i = 1; i <= n; i++) {
      for (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]);
      }
    }
  }
  long long ans = max(a[1][n], b[1][n]);
  if (ans >= (1 << 29)) ans = -1;
  cout << ans << endl;
}
