#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
  int vis[405], n, m, railways = 0;
  queue<int> q;
  for (int i = 0; i < 405; i++) vis[i] = -1;
  vis[1] = 0;
  vector<int> v[405];
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
    if ((a == 1 && b == n) || (a == n && b == 1)) railways = 1;
  }
  q.push(1);
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    if (railways != 1) {
      for (int i = 0; i < v[curr].size(); i++) {
        if (vis[v[curr][i]] == -1) {
          vis[v[curr][i]] = vis[curr] + 1;
          q.push(v[curr][i]);
        }
      }
    } else {
      set<int> s;
      for (int i = 1; i <= n; i++) s.insert(i);
      for (int i = 0; i < v[curr].size(); i++) s.erase(v[curr][i]);
      set<int>::iterator it;
      for (it = s.begin(); it != s.end(); it++) {
        int y = *(it);
        if (vis[y] == -1) {
          vis[y] = vis[curr] + 1;
          q.push(y);
        }
      }
    }
  }
  cout << vis[n] << endl;
  return 0;
}
