#include <bits/stdc++.h>
using namespace std;
vector<int> bfs(vector<vector<int>> &E) {
  vector<int> ret(E.size(), 1000000000);
  ret[0] = 0;
  queue<int> Q;
  Q.push(0);
  while (Q.size() != 0) {
    int u = Q.front();
    Q.pop();
    for (int i = 0; i < (E[u].size()); ++i) {
      int v = E[u][i];
      if (ret[v] != 1000000000) continue;
      ret[v] = ret[u] + 1;
      Q.push(v);
    }
  }
  return ret;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<bool>> e(n, vector<bool>(n, false));
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--;
    b--;
    e[a][b] = true;
    e[b][a] = true;
  }
  vector<vector<int>> E1(n, vector<int>());
  auto E2 = E1;
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < (n); ++j) {
      if (i == j) continue;
      if (e[i][j])
        E1[i].push_back(j);
      else
        E2[i].push_back(j);
    }
  }
  vector<int> d1 = bfs(E1), d2 = bfs(E2);
  if (d1.back() == 1000000000 || d2.back() == 1000000000) {
    cout << -1 << endl;
    return 0;
  }
  for (int i = 0; i < (n); ++i) {
    vector<int> ne;
    for (int j = 0; j < (E1[i].size()); ++j) {
      if (d1[i] + 1 == d1[E1[i][j]]) ne.push_back(E1[i][j]);
    }
    ne.push_back(i);
    E1[i] = ne;
  }
  for (int i = 0; i < (n); ++i) {
    vector<int> ne;
    for (int j = 0; j < (E2[i].size()); ++j) {
      if (d2[i] + 1 == d2[E2[i][j]]) ne.push_back(E2[i][j]);
    }
    ne.push_back(i);
    E2[i] = ne;
  }
  vector<vector<int>> dp(n, vector<int>(n, 1000000000));
  dp[0][0] = 0;
  queue<pair<int, int>> Q;
  Q.emplace(0, 0);
  while (Q.size() != 0 || dp.back().back() == 1000000000) {
    int u = Q.front().first;
    int v = Q.front().second;
    Q.pop();
    for (int i = 0; i < (E1[u].size()); ++i) {
      for (int j = 0; j < (E2[v].size()); ++j) {
        int U = E1[u][i], V = E2[v][j];
        if (dp[U][V] != 1000000000) continue;
        if (U != n - 1 && U == V) continue;
        dp[U][V] = dp[u][v] + 1;
        Q.emplace(U, V);
      }
    }
  }
  cout << dp.back().back() << endl;
  return 0;
}
