#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
inline void add(int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
}
inline int mul(int x, int y) { return ((long long)x * y) % mod; }
int gcd(int a, int b) {
  if (b) return gcd(b, a % b);
  return a;
}
int power(int a, int p) {
  int ret = 1;
  while (p) {
    if (p & 1) ret = mul(ret, a);
    a = mul(a, a);
    p /= 2;
  }
  return ret;
}
int phi(int n) {
  int ret = n;
  int i = 2;
  if (n % i == 0) {
    ret -= ret / i;
    while (n % i == 0) n /= i;
  }
  for (i = 3; i * i <= n; i++)
    if (n % i == 0) {
      ret -= ret / i;
      while (n % i == 0) n /= i;
    }
  if (n > 1) ret -= ret / n;
  return ret;
}
bool E[400][400];
int D[2][400][400];
int main() {
  int N;
  scanf("%d", &N);
  int M;
  scanf("%d", &M);
  memset(D, 31, sizeof(D));
  queue<pair<pair<int, int>, int>> Q;
  int inf = D[0][0][0];
  ;
  D[0][0][0] = 0;
  while (M--) {
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    E[x - 1][y - 1] = E[y - 1][x - 1] = true;
  }
  Q.push({{0, 0}, 0});
  while (!Q.empty()) {
    int ty = Q.front().second;
    pair<int, int> a = Q.front().first;
    Q.pop();
    int nd = D[ty][a.first][a.second] + 1;
    int x = a.first;
    int y = a.second;
    if (ty == 0) {
      if (x != N - 1) {
        for (int i = 0; i < N; i++)
          if (i != x and E[x][i] == true and D[1][i][y] == inf) {
            D[1][i][y] = nd;
            Q.push({{i, y}, 1});
            ;
          }
      } else if (D[1][x][y] == inf) {
        D[1][x][y] = nd;
        Q.push({{x, y}, 1});
      }
    }
    if (ty == 1) {
      if (x == N - 1 and E[y][N - 1] == false) {
        cout << nd / 2 << endl;
        return 0;
      }
      if (y != N - 1) {
        for (int i = 0; i < N; i++)
          if (i != x and i != y and E[y][i] == false and D[0][x][i] == inf) {
            D[0][x][i] = nd;
            Q.push({{x, i}, 0});
            ;
          }
      } else if (D[0][x][y] == inf) {
        D[0][x][y] = nd;
        Q.push({{x, y}, 0});
      }
    }
  }
  cout << -1 << endl;
  return 0;
}
