#include <bits/stdc++.h>
using namespace std;
int used[444], d[444], p[2][444], n, m;
vector<int> g[2][444];
map<pair<int, int>, bool> usd;
vector<int> vec[2];
void bfs(int k, int u) {
  memset(used, 0, sizeof used);
  memset(d, 0, sizeof d);
  queue<int> q;
  q.push(u);
  used[u] = true;
  p[k][1] = 1;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[k][v].size(); i++) {
      int to = g[k][v][i];
      if (!used[to]) {
        used[to] = true;
        d[to] = d[v] + 1;
        p[k][to] = v;
        q.push(to);
      }
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[0][u].push_back(v);
    g[0][v].push_back(u);
    usd[make_pair(u, v)] = usd[make_pair(v, u)] = true;
  }
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      if (!usd[make_pair(i, j)]) {
        g[1][i].push_back(j);
        g[1][j].push_back(i);
      }
    }
  for (int i = 1; i <= n; i++) {
    sort(g[0][i].begin(), g[0][i].end());
    sort(g[1][i].begin(), g[1][i].end());
    reverse(g[1][i].begin(), g[1][i].end());
  }
  bfs(0, 1);
  if (!used[n]) {
    cout << -1;
    return 0;
  }
  bfs(1, 1);
  if (!used[n]) {
    cout << -1;
    return 0;
  }
  int v = n;
  while (v != 1) {
    vec[0].push_back(p[0][v]);
    v = p[0][v];
  }
  v = n;
  while (v != 1) {
    vec[1].push_back(p[1][v]);
    v = p[1][v];
  }
  int ans1 = vec[0].size(), ans2 = vec[1].size();
  for (int i = 0; i < min(ans1 - 1, ans2 - 1); i++) {
    if (vec[0][i] == vec[1][i]) {
      cout << max(min(ans1, ans2) + 2, max(ans1, ans2));
      return 0;
    }
  }
  cout << max(ans1, ans2);
  return 0;
}
