#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int N = 4e3 + 5;
int n, m, a, b, ans = 1e9;
vector<int> gr[2][N];
bool used[N];
void bfs(bool f, int i = 1, int depth = 0) {
  queue<pii> q;
  q.emplace(i, depth);
  while (q.size()) {
    auto [v, d] = q.front();
    q.pop();
    if (used[v]) continue;
    used[v] = true;
    if (v == n) ans = min(ans, d);
    for (int u : gr[f][v]) q.emplace(u, d + 1);
  }
}
void Solve() {
  cin >> n >> m;
  while (m--) {
    cin >> a >> b;
    gr[1][a].push_back(b);
    gr[1][b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    sort(gr[1][i].begin(), gr[1][i].end());
    for (int j = 1, id = 0; j <= n; j++) {
      if (id < gr[1][i].size() && gr[1][i][id] == j) {
        id++;
        continue;
      }
      gr[0][i].push_back(j);
    }
  }
  bfs(find(gr[1][1].begin(), gr[1][1].end(), n) == gr[1][1].end());
  if (ans != 1e9)
    cout << ans;
  else
    cout << -1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  Solve();
  return 0;
}
