#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000")
#pragma warning(disable : 6031)
#pragma warning(disable : 4244)
#pragma warning(disable : 26451)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long mod = int(1e9) + 7;
const int INF = 1e9;
const long long LINF = 1e18;
int dist(int from, int to, vector<set<int>>& g) {
  int n = (int)(g).size();
  vector<int> dist(n, INF);
  dist[from] = 0;
  set<pair<int, int>> cur;
  cur.insert({0, 0});
  while (!cur.empty()) {
    set<pair<int, int>> nx;
    for (auto [u, d] : cur) {
      for (auto v : g[u]) {
        if (v == to) return d + 1;
        if (d + 1 >= dist[v]) continue;
        dist[v] = d + 1;
        nx.insert({v, d + 1});
      }
    }
    cur = nx;
  }
  return -1;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << setprecision(18) << fixed;
  int n, m;
  cin >> n >> m;
  vector<set<int>> ga(n), gr(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    gr[u].insert(v);
    gr[v].insert(u);
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      if (!gr[i].count(j)) ga[i].insert(j);
    }
  int dr = dist(0, n - 1, gr);
  int da = dist(0, n - 1, ga);
  if (dr == -1 || da == -1) {
    cout << -1;
    return 0;
  }
  cout << max(1, max(dr, da));
  return 0;
}
