#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long mcm(long long a, long long b) { return a * b / gcd(a, b); }
long long sq(long long a) { return a * a; }
long long pot(long long a, long long b) {
  return b ? sq(pot(a, b >> 1)) * (b & 1 ? a : 1) : 1;
}
long long potMod(long long a, long long e) {
  return e ? ((sq(potMod(a, e >> 1)) % 1000000007) * (e & 1 ? a : 1)) %
                 1000000007
           : 1;
}
int dist[500];
bool h[500], arc[500][500];
int bfs(vector<int> *g, int ini, int fin) {
  memset(dist, -1, sizeof(dist));
  memset(h, false, sizeof(h));
  dist[ini] = 0;
  queue<int> cola;
  cola.push(ini);
  while (!cola.empty()) {
    int c = cola.front();
    cola.pop();
    h[c] = true;
    for (int i = 0; i < g[c].size(); i += 1) {
      if (!h[g[c][i]] && dist[g[c][i]] == -1) {
        cola.push(g[c][i]);
        dist[g[c][i]] = dist[c] + 1;
      }
    }
  }
  return dist[fin];
}
int n, m, a, b;
vector<int> g[500];
int main() {
  memset(arc, false, sizeof(arc));
  cin >> n >> m;
  for (int i = 0; i < m; i += 1) {
    cin >> a >> b;
    a--;
    b--;
    arc[a][b] = true;
    arc[b][a] = true;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if (!arc[0][n - 1]) {
    printf("%d\n", bfs(g, 0, n - 1));
  } else {
    vector<int> B[500];
    for (int i = 0; i < n; i += 1) {
      for (int j = 0; j < n; j += 1) {
        if (!arc[i][j]) {
          B[i].push_back(j);
          B[j].push_back(i);
        }
      }
    }
    printf("%d\n", bfs(B, 0, n - 1));
  }
}
