#include <bits/stdc++.h>
using namespace std;
const int INF = 50000;
int e[400][400];
int n, m;
int d[400][2];
int add[400][2];
void Dijkstra(int x) {
  auto lam = [=](pair<int, int> a, pair<int, int> b) {
    if (d[a.first][a.second] == d[b.first][b.second])
      return (a.first == b.first ? a.second < b.second : a.first < b.first);
    else
      return d[a.first][a.second] < d[b.first][b.second];
  };
  set<pair<int, int>, decltype(lam)> s(lam);
  d[x][0] = d[x][1] = 0;
  s.insert({x, 0});
  s.insert({x, 1});
  add[x][0] = add[x][1] = 1;
  while (s.size()) {
    pair<int, int> y;
    y = *s.begin();
    add[y.first][y.second] = 2;
    s.erase(s.begin());
    for (int i = 0; i < n; i++) {
      if (i == y.first) continue;
      if (e[y.first][i] != y.second) continue;
      int t = i;
      if (add[t][y.second] == 0) {
        if (d[y.first][y.second] + 1 == d[t][!y.second])
          d[t][y.second] = min(d[y.first][y.second] + 3, d[t][y.second]);
        else
          d[t][y.second] = d[y.first][y.second] + 1;
        s.insert({t, y.second});
        add[t][y.second] = 1;
      } else if (add[t][y.second] == 2)
        continue;
      else if (d[y.first][y.second] + 1 < d[t][y.second]) {
        s.erase(s.find({t, y.second}));
        if (d[y.first][y.second] + 1 == d[t][!y.second])
          d[t][y.second] = min(d[y.first][y.second] + 3, d[t][y.second]);
        else
          d[t][y.second] = d[y.first][y.second] + 1;
        s.insert({t, y.second});
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    e[u][v] = 1;
    e[v][u] = 1;
  }
  for (int i = 0; i < n; i++) d[i][0] = d[i][1] = INF;
  Dijkstra(0);
  int x = max(d[n - 1][0], d[n - 1][1]);
  if (x == INF)
    cout << "-1";
  else
    cout << x;
  return 0;
}
