#include <bits/stdc++.h>
using namespace std;
const int N = 407, M = N * N * 2 * 2;
int mp[N][N], cnt, h1[N], h2[N], q[N], n, m;
struct data {
  int to, next;
} e[M];
struct graph {
  int head[N];
  void ins(int u, int v) {
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
  }
  void insert(int u, int v) {
    ins(u, v);
    ins(v, u);
  }
} g1, g2;
void bfs(graph& g, int h[]) {
  for (int i = 0; i < N; ++i) h[i] = -1;
  int t = 0, w = 1;
  q[0] = 1;
  h[1] = 0;
  while (t != w) {
    int now = q[t++];
    for (int i = g.head[now]; i; i = e[i].next)
      if (h[e[i].to] == -1) {
        h[e[i].to] = h[now] + 1;
        q[w++] = e[i].to;
      }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    g1.insert(u, v);
    mp[u][v] = mp[v][u] = 1;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (!mp[i][j]) g2.insert(i, j);
  bfs(g1, h1);
  bfs(g2, h2);
  if (h1[n] == -1 || h2[n] == -1)
    cout << -1 << endl;
  else
    cout << max(h1[n], h2[n]) << endl;
  return 0;
}
