#include <bits/stdc++.h>
using namespace std;
long long int inf = pow(10, 9) + 7, n;
vector<vector<long long int>> v, v1;
map<long long int, long long int> level;
vector<long long int> ans;
vector<bool> vis;
long long int bfs(long long int r, vector<vector<long long int>> &a,
                  long long int cnt) {
  queue<long long int> q;
  q.push(r);
  vis[r] = true;
  level[r] = 0;
  while (!q.empty()) {
    long long int p = q.front();
    q.pop();
    for (long long int i = 0; i < a[p].size(); ++i) {
      if (vis[a[p][i]] == false) {
        q.push(a[p][i]);
        level[a[p][i]] = level[p] + 1;
        vis[a[p][i]] = true;
      }
    }
  }
  if (level.find(n) == level.end()) return -1;
  return level[n];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int m;
  cin >> n >> m;
  set<pair<long long int, long long int>> se;
  for (long long int i = 1; i <= n - 1; ++i) {
    for (long long int j = i + 1; j <= n; ++j) se.insert({i, j});
  }
  v.resize(n + 1);
  v1.resize(n + 1);
  vis.resize(n + 1, false);
  for (long long int i = 0; i < m; ++i) {
    long long int x, y;
    cin >> x >> y;
    if (y < x) swap(x, y);
    se.erase(se.find({x, y}));
    v[x].push_back(y);
    v[y].push_back(x);
  }
  for (auto i = se.begin(); i != se.end(); ++i) {
    v1[i->first].push_back(i->second);
    v1[i->second].push_back(i->first);
  }
  cout << (se.find({1, n}) != se.end() ? bfs(1, v, 0) : bfs(1, v1, 0));
  return 0;
}
