#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const long long mod = 1e9 + 7;
inline long long bigmod(long long B, long long P) {
  long long R = 1;
  while (P > 0) {
    if (P & 1) {
      R = (R * B) % mod;
    }
    P >>= 1;
    B = (B * B) % mod;
  }
  return R;
}
const long long mxn = 500;
long long Mod(long long a) {
  if (a < 0)
    return (a + mod) % mod;
  else
    return a % mod;
}
long long Mul(long long a, long long b) { return Mod(Mod(a) * Mod(b)); }
long long Add(long long a, long long b) { return Mod(Mod(a) + Mod(b)); }
vector<long long> adj[mxn];
long long vis[mxn], pred[mxn], dist[mxn];
vector<long long> adj2[mxn];
long long vis2[mxn], pred2[mxn], dist2[mxn];
long long n;
bool bfs(long long root) {
  queue<long long> q;
  q.push(root);
  vis[root] = 1;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    for (long long v : adj[u]) {
      if (!vis[v]) {
        vis[v] = 1;
        dist[v] = dist[u] + 1;
        q.push(v);
        if (v == n) return true;
      }
    }
  }
  return false;
}
bool bfs2(long long root) {
  queue<long long> q;
  q.push(root);
  vis2[root] = 1;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    for (long long v : adj2[u]) {
      if (!vis2[v]) {
        vis2[v] = 1;
        dist2[v] = dist2[u] + 1;
        q.push(v);
        if (v == n) return true;
      }
    }
  }
  return false;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long tt = 1;
  for (long long tc = 1; tc <= tt; tc++) {
    long long m, f = 0;
    cin >> n >> m;
    map<pair<long long, long long>, bool> trainase;
    for (long long i = 0; i < m; i++) {
      long long u, v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
      trainase[{u, v}] = 1;
      trainase[{v, u}] = 1;
      if (u == n || v == n) f = 1;
    }
    if (!f)
      cout << -1 << '\n';
    else {
      for (long long i = 1; i <= n; i++) {
        for (long long j = i + 1; j <= n; j++) {
          if (!trainase[{i, j}]) {
            adj2[i].push_back(j);
            adj2[j].push_back(i);
          }
        }
      }
      if (!bfs2(1) || !bfs(1)) {
        cout << -1 << '\n';
        return 0;
      }
      bfs(1);
      bfs2(1);
      cout << max(dist2[n], dist[n]) << '\n';
    }
  }
  return 0;
}
