#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.1415926535897923846;
const long long int MOD = 1000000007;
const long long int N = 998244353;
long long int power(long long int x, long long int n) {
  long long int res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}
long long int modinverse(long long int a) { return power(a, MOD - 2); }
vector<vector<long long int> > adj1, adj2;
map<pair<long long int, long long int>, long long int> mp1;
long long int n, m;
void solve() {
  cin >> n >> m;
  adj1.resize(n);
  adj2.resize(n);
  for (long long int i = 0; i < m; i++) {
    long long int u, v;
    cin >> u >> v;
    --u, --v;
    adj1[u].push_back(v);
    adj1[v].push_back(u);
    mp1[{u, v}]++;
    mp1[{v, u}]++;
  }
  for (long long int i = 0; i < n; i++) {
    for (long long int j = i + 1; j < n; j++) {
      if (mp1[{i, j}] == 0) {
        adj2[i].push_back(j);
        adj2[j].push_back(i);
      }
    }
  }
  vector<long long int> d1(n, (long long int)1e18);
  vector<long long int> d2(n, (long long int)1e18);
  d1[0] = 0;
  set<pair<long long int, long long int> > s1;
  s1.insert({0, 0});
  while (!s1.empty()) {
    pair<long long int, long long int> p = *s1.begin();
    s1.erase(s1.begin());
    long long int dis = p.first, node = p.second;
    if (d1[node] != dis) continue;
    for (auto x : adj1[node]) {
      if (d1[node] + 1 < d1[x]) {
        d1[x] = d1[node] + 1;
        s1.insert({d1[x], x});
      }
    }
  }
  d2[0] = 0;
  set<pair<long long int, long long int> > s2;
  s2.insert({0, 0});
  while (!s2.empty()) {
    pair<long long int, long long int> p = *s2.begin();
    s2.erase(s2.begin());
    long long int dis = p.first, node = p.second;
    if (d2[node] != dis) continue;
    for (auto x : adj2[node]) {
      if (d2[node] + 1 < d2[x]) {
        d2[x] = d2[node] + 1;
        s2.insert({d2[x], x});
      }
    }
  }
  if (d1[n - 1] == (long long int)1e18 || d2[n - 1] == (long long int)1e18) {
    cout << -1 << endl;
    return;
  } else {
    cout << max(d1[n - 1], d2[n - 1]) << endl;
    return;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int test = 1;
  while (test--) {
    solve();
  }
  cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
}
