#include <bits/stdc++.h>
using namespace std;
const int N = 410, M = 500010;
int n, m, Tcnt, Bcnt;
int Thead[N], Bhead[N], dis[N], a[N][N];
bool vis[N];
struct Edge {
  int to, nex;
} Te[M], Be[M];
inline void Tadd(int x, int y) {
  Te[++Tcnt].to = y;
  Te[Tcnt].nex = Thead[x];
  Thead[x] = Tcnt;
}
inline void Badd(int x, int y) {
  Be[++Bcnt].to = y;
  Be[Bcnt].nex = Bhead[x];
  Bhead[x] = Bcnt;
}
inline int spfaT(int s) {
  queue<int> q;
  q.push(s);
  memset(vis, 0, sizeof vis);
  vis[s] = 1;
  memset(dis, 0x3f, sizeof dis);
  dis[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = Thead[u]; i; i = Te[i].nex) {
      int v = Te[i].to;
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
  return dis[n];
}
inline int spfaB(int s) {
  queue<int> q;
  q.push(s);
  memset(vis, 0, sizeof vis);
  vis[s] = 1;
  memset(dis, 0x3f, sizeof dis);
  dis[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = Bhead[u]; i; i = Be[i].nex) {
      int v = Be[i].to;
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
  return dis[n];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[x][y] = 1;
    a[y][x] = 1;
    Tadd(x, y);
    Tadd(y, x);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (i == j || a[i][j]) continue;
      Badd(i, j);
      Badd(j, i);
    }
  int x, y;
  x = spfaT(1);
  y = spfaB(1);
  if (x > 1e9 || y > 1e9)
    puts("-1");
  else
    printf("%d\n", max(x, y));
  return 0;
}
