#include <bits/stdc++.h>
using namespace std;
int n, m, a[401][401];
int f1(int dist[], bool vis[]) {
  int mi = INT_MAX, x;
  for (int i = 0; i < n; i++) {
    if (vis[i] == false && dist[i] <= mi) {
      mi = dist[i];
      x = i;
    }
  }
  return x;
}
int f(int s) {
  int dist[100001];
  int i, j;
  bool vis[100001];
  for (i = 0; i < n; i++) {
    dist[i] = INT_MAX;
    vis[i] = false;
  }
  dist[s] = 0;
  for (i = 0; i < n - 1; i++) {
    int x = f1(dist, vis);
    vis[x] = true;
    for (j = 0; j < n; j++) {
      if (vis[j] == false && a[x][j] == 1 && dist[x] != INT_MAX &&
          dist[x] + a[x][j] < dist[j]) {
        dist[j] = dist[x] + a[x][j];
      }
    }
  }
  return dist[n - 1];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long i, j, k;
  cin >> n >> m;
  for (i = 0; i < m; i++) {
    long long x, y;
    cin >> x >> y;
    a[x - 1][y - 1] = 1;
    a[y - 1][x - 1] = 1;
  }
  int x = f(0);
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if (a[i][j] == 0)
        a[i][j] = 1;
      else
        a[i][j] = 0;
    }
  }
  int y = f(0);
  if (x == INT_MAX || y == INT_MAX)
    cout << -1 << "\n";
  else
    cout << max(y, x) << "\n";
  return 0;
}
