#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans[2];
int vis[4005];
int mp[4005][4005];
int arv[2][4005];
int pre[4005];
int dijkstra(int mod) {
  memset(vis, 0, sizeof(vis));
  memset(pre, 0, sizeof(pre));
  int dis[4005];
  for (int i = 1; i <= n; i++) {
    dis[i] = mp[1][i];
  }
  vis[1] = 1;
  for (int i = 0; i < n - 1; i++) {
    int mi = 1000000000, u;
    for (int i = 1; i <= n; i++) {
      if (vis[i]) continue;
      if (dis[i] < mi) {
        mi = dis[i];
        u = i;
      }
    }
    vis[u] = 1;
    for (int i = 1; i <= n; i++) {
      if (mi + mp[u][i] < dis[i]) {
        pre[i] = u;
        dis[i] = mi + mp[u][i];
      }
    }
  }
  int t = n, cnt = 0;
  while (pre[t] && cnt < 400) {
    arv[mod][cnt++] = pre[t];
    t = pre[t];
  }
  return dis[n];
}
int main() {
  int u, v;
  ans[0] = 1000000000, ans[1] = 1000000000;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      mp[i][j] = (i == j) ? 0 : 1000000000;
    }
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &u, &v);
    mp[u][v] = 1;
    mp[v][u] = 1;
  }
  ans[0] = dijkstra(0);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (mp[i][j] == 1000000000) {
        mp[i][j] = 1;
      } else if (mp[i][j] == 1) {
        mp[i][j] = 1000000000;
      }
    }
  }
  ans[1] = dijkstra(1);
  for (int i = 0; arv[0][i] && arv[1][i] && i < 400; i++) {
    if (arv[0][i] == arv[1][i]) {
      if (ans[0] < ans[1]) {
        ans[0]++;
      } else {
        ans[1]++;
      }
    }
  }
  if (ans[0] >= 1000000000 || ans[1] >= 1000000000) {
    puts("-1");
  } else {
    printf("%d\n", max(ans[0], ans[1]));
  }
  return 0;
}
