#include <bits/stdc++.h>
using namespace std;
const int M = 405;
int n, m;
bool g1[M][M], g2[M][M];
int bfs(bool g[M][M]) {
  queue<int> bfs;
  int dis[M];
  memset(dis, -1, sizeof(dis));
  bfs.push(1), bfs.push(0);
  dis[1] = 0;
  while (!bfs.empty()) {
    int x = bfs.front();
    bfs.pop();
    int t = bfs.front();
    bfs.pop();
    if (t > dis[x]) continue;
    for (int i = 1; i <= n; ++i) {
      if (!g[x][i]) continue;
      if (t + 1 < dis[i] || dis[i] == -1) {
        dis[i] = t + 1;
        if (i == n) return t + 1;
        bfs.push(i);
        bfs.push(t + 1);
      }
    }
  }
  return -1;
}
int main() {
  cin >> n >> m;
  for (int i = 0, x, y; i < m; ++i) {
    cin >> x >> y;
    g1[x][y] = g1[y][x] = true;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) g2[i][j] = !g1[i][j];
  }
  if (g1[1][n])
    cout << bfs(g2) << endl;
  else
    cout << bfs(g1) << endl;
}
