#include <bits/stdc++.h>
using namespace std;
const int MAX = 401;
int adj[MAX][MAX];
vector<vector<int> > car(MAX, vector<int>()), train(MAX, vector<int>());
int N;
int dist1[MAX], prev1[MAX], dist2[MAX], prev2[MAX];
int vol[MAX];
void djik(int source, vector<vector<int> > &graph, int *dist, int *prev) {
  dist[source] = 0;
  prev[source] = -1;
  bool done[MAX];
  memset(done, 0, sizeof(done));
  for (;;) {
    int mini = ((int)1e9 + 10);
    int small;
    for (int(i) = (1); (i) < (N + 1); (i)++) {
      if (!done[i] && dist[i] < mini) {
        mini = dist[i];
        small = i;
      }
    }
    if (mini == ((int)1e9 + 10)) break;
    done[small] = 1;
    for (auto &target : (graph[small])) {
      if (dist[target] > dist[small] + 1) {
        dist[target] = dist[small] + 1;
        prev[target] = small;
      }
    }
  }
}
void djik2(int source, vector<vector<int> > &graph, int *dist,
           int *dist_from_other) {
  dist[source] = 0;
  bool done[MAX];
  memset(done, 0, sizeof(done));
  for (;;) {
    int mini = ((int)1e9 + 10);
    int small;
    for (int(i) = (1); (i) < (N + 1); (i)++)
      if (!done[i] && dist[i] < mini) {
        mini = dist[i];
        small = i;
      }
    if (mini == ((int)1e9 + 10)) break;
    done[small] = 1;
    for (auto &target : (graph[small])) {
      if (dist[target] > dist[small] + 1 &&
          !(vol[target] && dist[small] + 1 == dist_from_other[target])) {
        dist[target] = dist[small] + 1;
      }
    }
  }
}
int main() {
  int n;
  scanf("%d", &(n));
  ;
  int m;
  scanf("%d", &(m));
  ;
  N = n;
  int cnt = 0;
  for (int(i) = (0); (i) < (MAX); (i)++) dist1[i] = dist2[i] = ((int)1e9 + 10);
  for (int(i) = (0); (i) < (m); (i)++) {
    int a;
    scanf("%d", &(a));
    ;
    int b;
    scanf("%d", &(b));
    ;
    adj[a][b] = adj[b][a] = 1;
    train[a].push_back(b);
    train[b].push_back(a);
    cnt += 2;
  }
  for (int(i) = (1); (i) < (n + 1); (i)++)
    for (int(j) = (1); (j) < (n + 1); (j)++)
      if (!adj[i][j] && i != j) {
        car[i].push_back(j);
        cnt++;
      }
  memset(prev1, -1, sizeof(prev1));
  memset(prev2, -1, sizeof(prev2));
  djik(1, train, dist1, prev1);
  int cur = prev1[n];
  while (cur != 1 && cur != -1) {
    vol[cur] = 1;
    cur = prev1[cur];
  }
  djik2(1, car, dist2, dist1);
  int ans = max(dist1[n], dist2[n]);
  for (int(i) = (0); (i) < (MAX); (i)++) dist1[i] = dist2[i] = ((int)1e9 + 10);
  memset(prev1, -1, sizeof(prev1));
  memset(prev2, -1, sizeof(prev2));
  memset(vol, 0, sizeof(vol));
  djik(1, car, dist1, prev1);
  cur = prev1[n];
  while (cur != 1 && cur != -1) {
    vol[cur] = 1;
    cur = prev1[cur];
  }
  djik2(1, train, dist2, dist1);
  int ans2 = max(dist1[n], dist2[n]);
  int wow = max(ans, ans2);
  if (wow == ((int)1e9 + 10)) {
    cout << (-1) << "\n";
    ;
  } else {
    cout << (wow) << "\n";
    ;
  }
}
