#include <bits/stdc++.h>
using namespace std;
int m[405][405];
int bfs(vector<int> g[], int n) {
  int s = 1;
  int d[n + 1];
  bool visited[n + 1];
  for (int i = 0; i <= n; i++) {
    d[i] = 1e9;
    visited[i] = false;
  }
  queue<int> q;
  q.push(1);
  d[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    visited[u] = true;
    for (int i : g[u]) {
      if (visited[i] == false) {
        q.push(i);
      }
      if (d[u] + 1 < d[i]) d[i] = d[u] + 1;
      if (i == n) return d[n];
    }
  }
  if (d[n] == 1e9)
    return -1;
  else
    return d[n];
}
int main() {
  int n, m1;
  cin >> n >> m1;
  vector<int> g[n + 1], g1[n + 1];
  for (int i = 0; i < m1; i++) {
    int a, b;
    cin >> a >> b;
    m[a][b] = 1;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (m[i][j] == 0 && m[j][i] == 0) {
        g1[i].push_back(j);
        g1[j].push_back(i);
      }
    }
  }
  int t;
  if (m[1][n] || m[n][1])
    t = 1;
  else
    t = bfs(g, n);
  int t1 = bfs(g1, n);
  if (t == -1 || t1 == -1)
    cout << "-1";
  else {
    if (t > t1)
      cout << t;
    else
      cout << t1;
  }
}
