#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long N = 3e5 + 5;
const long long INF = 1e14;
long long dist[405];
vector<long long> adj[405];
bool vis[405];
void init() {
  for (long long i = 0; i < 405; i++) {
    dist[i] = INF;
    vis[i] = false;
  }
}
void bfs(long long s) {
  queue<long long> q;
  q.push(s);
  dist[s] = 0;
  vis[s] = true;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    for (long long i = 0; i < adj[u].size(); i++) {
      long long v = adj[u][i];
      if (vis[v]) continue;
      dist[v] = dist[u] + 1;
      vis[v] = true;
      q.push(v);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  long long n, m;
  cin >> n >> m;
  for (long long i = 0; i < m; i++) {
    long long a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (long long i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end());
  init();
  bfs(0);
  long long ans = dist[n - 1];
  for (long long i = 0; i < n; i++) {
    vector<long long> temp = adj[i];
    adj[i].clear();
    long long st = 0;
    for (long long j = 0; j < n; j++) {
      if (j == i) continue;
      if (st < temp.size()) {
        if (j == temp[st]) {
          st++;
          continue;
        }
      }
      adj[i].push_back(j);
    }
  }
  init();
  bfs(0);
  ans = max(ans, dist[n - 1]);
  if (ans == INF) ans = -1;
  cout << ans << "\n";
  return 0;
}
