#include <bits/stdc++.h>
using namespace std;
int ara[500005];
bool vis[401][401];
bool b[401];
int bus[401];
int rail[401];
vector<int> railway[401], road[401];
void BFS(int s, int d) {
  for (int i = 0; i <= d; i++) {
    bus[i] = 10000000;
    b[i] = false;
  }
  int prnt[401];
  bus[s] = 0;
  queue<int> Q;
  Q.push(s);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = 0; i < road[u].size(); i++) {
      int v = road[u][i];
      if (bus[v] > bus[u] + 1) {
        bus[v] = bus[u] + 1;
        prnt[v] = u;
        Q.push(v);
      }
    }
  }
  if (bus[d] == 10000000) return;
  int x = d;
  while (true) {
    if (x != d) b[x] = true;
    if (x == s) return;
    x = prnt[x];
  }
}
void BFS1(int s, int d) {
  for (int i = 0; i <= d; i++) rail[i] = 10000000;
  rail[s] = 0;
  queue<int> Q;
  Q.push(s);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = 0; i < railway[u].size(); i++) {
      int v = railway[u][i];
      if (rail[v] > rail[u] + 1 and !b[v]) {
        rail[v] = rail[u] + 1;
        Q.push(v);
      }
    }
  }
}
int main() {
  string str;
  int n, m, k;
  while (cin >> n >> m) {
    memset(vis, false, sizeof(vis));
    for (int i = 0; i <= n; i++) {
      railway[i].clear();
      road[i].clear();
    }
    int u, v;
    for (int i = 0; i < m; i++) {
      cin >> u >> v;
      railway[u].push_back(v);
      railway[v].push_back(u);
      vis[u][v] = true;
      vis[v][u] = true;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (i != j and !vis[i][j]) {
          road[i].push_back(j);
        }
      }
    }
    BFS(1, n);
    BFS1(1, n);
    if (bus[n] != 10000000 and rail[n] != 10000000)
      cout << max(bus[n], rail[n]) << endl;
    else
      cout << -1 << endl;
  }
  return 0;
}
