#include <bits/stdc++.h>
using namespace std;
const int M = 405;
int n, m, dist[M];
int bfs(vector<int> adj[]) {
  fill(dist, dist + M, 1e8);
  dist[1] = 0;
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (auto u : adj[node]) {
      if (dist[u] > dist[node] + 1) {
        dist[u] = dist[node] + 1;
        q.push(u);
      }
    }
  }
  return dist[n];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  vector<int> rail[M], bus[M];
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    rail[u].push_back(v);
    rail[v].push_back(u);
  }
  bool poss = true;
  for (int twn = 1; twn <= n; twn++) {
    set<int> s;
    for (int i = 1; i <= n; i++)
      if (i != twn) s.insert(i);
    for (auto u : rail[twn]) s.erase(s.find(u));
    for (auto i : s) {
      bus[twn].push_back(i);
      bus[i].push_back(twn);
    }
  }
  if (!bus[1].size() || !bus[n].size()) return cout << -1, 0;
  int r = bfs(rail);
  int b = bfs(bus);
  if (r == 1e8 || b == 1e8) return cout << -1, 0;
  cout << max(r, b) << endl;
  return 0;
}
