#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
const int maxm = 100000;
const int INF = 0x3f3f3f3f;
struct Edge {
  int next, v;
  Edge() {}
  Edge(int next, int v) : next(next), v(v) {}
} e[maxm << 1];
int n, m;
int head[maxn], cnt;
int dis[maxn];
bool exis[maxn][maxn], inq[maxn];
int q[maxm], front, tail;
inline int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void AddEdge(int u, int v) {
  e[++cnt] = Edge(head[u], v);
  head[u] = cnt;
  e[++cnt] = Edge(head[v], u);
  head[v] = cnt;
}
inline int SPFA() {
  memset(dis, INF, sizeof(dis));
  front = tail = 0;
  dis[1] = 0;
  q[++tail] = 1;
  while (front != tail) {
    int u = q[++front];
    inq[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        if (!inq[v]) {
          inq[v] = 1;
          q[++tail] = v;
        }
      }
    }
  }
  return dis[n];
}
int main() {
  if (fopen("in.in", "r") != NULL) {
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
  }
  n = read(), m = read();
  for (int i = 1, u, v; i <= m; i++) {
    u = read(), v = read();
    exis[u][v] = exis[v][u] = 1;
  }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      if (!exis[i][j]) AddEdge(i, j);
  int ans = SPFA();
  for (int i = 0; i <= n; i++) head[i] = 0;
  cnt = 0;
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      if (exis[i][j]) AddEdge(i, j);
  ans = max(ans, SPFA());
  printf("%d\n", ans == INF ? -1 : ans);
  return 0;
}
