#include <bits/stdc++.h>
using namespace std;
map<long long int, long long int> rail_path;
map<long long int, long long int> roads_path;
long long int digit[10];
vector<char> ans_rps;
long long int fibo[100009];
long long int ans_sum[100009];
long long int ar[109];
vector<long long int> rail[409];
vector<long long int> roads[409];
long long int check[409][409];
long long int rail_distance[409];
long long int roads_distance[409];
long long int init = -1;
void bfs1(long long int src) {
  long long int u, v, w, x, y, z, j;
  memset(rail_distance, init, sizeof(rail_distance));
  queue<long long int> q;
  rail_distance[src] = 0;
  q.push(src);
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (j = 0; j < rail[u].size(); j++) {
      v = rail[u][j];
      if (rail_distance[v] == -1) {
        rail_distance[v] = rail_distance[u] + 1;
        q.push(v);
      }
    }
  }
}
void bfs2(long long int src) {
  long long int u, v, w, x, y, z, j;
  queue<long long int> q2;
  memset(roads_distance, init, sizeof(roads_distance));
  roads_distance[src] = 0;
  q2.push(src);
  while (!q2.empty()) {
    u = q2.front();
    q2.pop();
    for (j = 0; j < roads[u].size(); j++) {
      v = roads[u][j];
      if (roads_distance[v] == -1) {
        roads_distance[v] = roads_distance[u] + 1;
        q2.push(v);
      }
    }
  }
}
int main() {
  long long int n, i, j, k, l, p = 1000000007, q = 0, s = 0, r, ts, max_val = 0,
                               min_val = 1000000009, x, y, t, d, even = 0,
                               odd = 0, position, three = 3, sum = 0, nine = 9,
                               one = 1, pos1, pos2, a = 2, b = 1, c = 0, z;
  long long int a1, a2, k1, k2, a1k1, a2k2, b1, b2, m;
  string s1, t1;
  cin >> n >> m;
  for (i = 1; i <= m; i++) {
    cin >> x >> y;
    rail[x].push_back(y);
    rail[y].push_back(x);
    check[x][y] = 1;
    check[y][x] = 1;
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if (check[i][j] == 0 && check[j][i] == 0 && i != j) {
        roads[i].push_back(j);
        roads[j].push_back(i);
        check[i][j] = 1;
        check[j][i] = 1;
      }
    }
  }
  bfs1(b);
  bfs2(b);
  if (roads_distance[n] == -1 || rail_distance[n] == -1)
    cout << "-1";
  else
    cout << max(roads_distance[n], rail_distance[n]);
}
