#include <bits/stdc++.h>
using namespace std;
int n, m;
set<pair<int, int> > s;
const int inf = 1e9;
vector<int> g[444], g2[444], d(444, inf), d2(444, inf);
queue<int> q, q2;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
    s.insert(make_pair(x, y));
    s.insert(make_pair(y, x));
  }
  for (int i = 1; i < n; i++)
    for (int j = i + 1; j <= n; j++)
      if (!s.count(make_pair(i, j))) {
        g2[i].push_back(j);
        g2[j].push_back(i);
        s.insert(make_pair(i, j));
        s.insert(make_pair(j, i));
      }
  if (g2[n].size() == 0) {
    cout << -1;
    return 0;
  }
  q.push(1);
  q2.push(1);
  d[1] = 0;
  d2[1] = 0;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int to = g[v][i];
      if (d[to] == inf) {
        d[to] = d[v] + 1;
        q.push(to);
      }
    }
  }
  while (!q2.empty()) {
    int v = q2.front();
    q2.pop();
    for (int i = 0; i < g2[v].size(); i++) {
      int to = g2[v][i];
      if (to == n && d[v] == inf) {
        d2[to] = d2[v] + 1;
        q2.push(to);
      } else {
        if (d2[to] == inf && d2[v] + 1 == d[to]) {
          d2[to] = d2[v] + 3;
          q2.push(to);
        }
        if (d2[to] == inf && d2[v] + 1 != d[to]) {
          d2[to] = d2[v] + 1;
          q2.push(to);
        }
      }
    }
  }
  if (d[n] == inf || d2[n] == inf) {
    cout << -1;
    return 0;
  }
  int ans = max(d[n], d2[n]);
  q.push(1);
  q2.push(1);
  for (int i = 1; i <= n; i++) {
    d[i] = inf;
    d2[i] = inf;
  }
  d[1] = 0;
  d2[1] = 0;
  while (!q2.empty()) {
    int v = q2.front();
    q2.pop();
    for (int i = 0; i < g2[v].size(); i++) {
      int to = g2[v][i];
      if (d2[to] == inf) {
        d2[to] = d2[v] + 1;
        q2.push(to);
      }
    }
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int to = g[v][i];
      if (to == n && d[v] == inf) {
        d[to] = d[v] + 1;
        q.push(to);
      } else {
        if (d[to] == inf && d[v] + 1 == d2[to]) {
          d[to] = d[v] + 3;
          q.push(to);
        }
        if (d[to] == inf && d[v] + 1 != d2[to]) {
          d[to] = d[v] + 1;
          q.push(to);
        }
      }
    }
  }
  if (d[n] == inf || d2[n] == inf) {
    cout << -1;
    return 0;
  }
  ans = min(ans, max(d[n], d2[n]));
  cout << ans;
  return 0;
}
