#include <bits/stdc++.h>
using namespace std;
vector<set<int> > F;
vector<set<int> > G;
vector<int> DisF;
vector<int> DisG;
void BFS(int s, vector<set<int> > &A, vector<int> &B) {
  queue<int> Q;
  B[s] = 0;
  Q.push(s);
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (set<int>::iterator it = A[x].begin(); it != A[x].end(); ++it) {
      if (B[*it] == -1) {
        B[*it] = B[x] + 1;
        Q.push(*it);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  F.resize(n + 1);
  G.resize(n + 1);
  DisF.resize(n + 1, -1);
  DisG.resize(n + 1, -1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
      F[i].insert(j);
    }
    for (int j = i + 1; j <= n; ++j) {
      F[i].insert(j);
    }
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    F[x].erase(y);
    F[y].erase(x);
    G[x].insert(y);
    G[y].insert(x);
  }
  BFS(1, F, DisF);
  BFS(1, G, DisG);
  if (DisG[n] != -1 && DisF[n] != -1) {
    cout << max(DisF[n], DisG[n]);
  } else {
    cout << -1;
  }
  return 0;
}
