#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
bool maxi(A &a, const B &b) {
  return (a < b) ? (a = b, true) : false;
};
template <class A, class B>
bool mini(A &a, const B &b) {
  return (a > b) ? (a = b, true) : false;
};
const int maxN = 405;
const int inf = 1e9;
int n, m, res = inf, d[maxN][maxN][2];
vector<int> railways[maxN], roads[maxN];
void Input() {
  int u, v;
  cin >> n >> m;
  for (int _ = (1), _b = (m); _ <= _b; ++_) {
    cin >> u >> v;
    railways[u].push_back(v);
    railways[v].push_back(u);
  }
}
void Solve() {
  queue<pair<pair<int, int>, int> > q;
  int x, y, flag;
  for (int u = (1), _b = (n); u <= _b; ++u) {
    vector<bool> vis(n + 5, false);
    for (const int &v : railways[u]) vis[v] = true;
    for (int v = (1), _b = (n); v <= _b; ++v) {
      if (v != u && !vis[v]) roads[u].push_back(v);
      for (int f = (0), _b = (1); f <= _b; ++f) d[u][v][f] = inf;
    }
  };
  d[1][1][0] = 0;
  q.push(pair<pair<int, int>, int>(pair<int, int>(1, 1), 0));
  while (!q.empty()) {
    x = q.front().first.first;
    y = q.front().first.second;
    flag = q.front().second;
    q.pop();
    if (!flag) {
      for (const int &z : railways[x])
        if (mini(d[z][y][1], d[x][y][0] + 1))
          q.push(pair<pair<int, int>, int>(pair<int, int>(z, y), 1));
    } else {
      for (const int &z : roads[y])
        if (z == n || z != x) {
          if (mini(d[x][z][0], d[x][y][1] + 1))
            q.push(pair<pair<int, int>, int>(pair<int, int>(x, z), 0));
        }
    }
  }
  mini(res, *min_element(d[n][n], d[n][n] + 2));
  for (int u = (1), _b = (n); u <= _b; ++u)
    for (int v = (1), _b = (n); v <= _b; ++v)
      for (int f = (0), _b = (1); f <= _b; ++f) d[u][v][f] = inf;
  d[1][1][0] = 0;
  q.push(pair<pair<int, int>, int>(pair<int, int>(1, 1), 0));
  while (!q.empty()) {
    x = q.front().first.first;
    y = q.front().first.second;
    flag = q.front().second;
    q.pop();
    if (!flag) {
      for (const int &z : roads[x])
        if (mini(d[z][y][1], d[x][y][0] + 1))
          q.push(pair<pair<int, int>, int>(pair<int, int>(z, y), 1));
    } else {
      for (const int &z : railways[y])
        if (z == n || z != x) {
          if (mini(d[x][z][0], d[x][y][1] + 1))
            q.push(pair<pair<int, int>, int>(pair<int, int>(x, z), 0));
        }
    }
  }
  mini(res, *min_element(d[n][n], d[n][n] + 2));
  cout << (res < inf ? ((res >> 1) + (res & 1)) : -1) << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Input();
  Solve();
  return 0;
}
