#include <bits/stdc++.h>
using namespace std;
const int MAXN = 410;
bool link[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dist[MAXN];
struct node {
  int u;
  int deep;
};
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d", &u);
    scanf("%d", &v);
    link[u][v] = true;
    link[v][u] = true;
  }
  memset(vis, false, sizeof(vis));
  memset(dist, -1, sizeof(dist));
  queue<node> q;
  for (int i = 1; i <= n; i++) {
    if (link[1][i]) {
      node d{i, 1};
      vis[1][i] = true;
      dist[i] = 1;
      q.push(d);
    }
  }
  while (!q.empty()) {
    node cur = q.front();
    q.pop();
    for (int i = 1; i <= n; i++) {
      node t = cur;
      if (link[cur.u][i] && !vis[cur.u][i]) {
        vis[cur.u][i] = true;
        if (dist[i] == -1)
          dist[i] = cur.deep + 1;
        else
          dist[i] = min(dist[i], cur.deep + 1);
        t.u = i;
        t.deep++;
        q.push(t);
      }
    }
  }
  int ans1, ans2;
  bool vaild = true;
  if (dist[n] == -1) {
    vaild = false;
  } else {
    ans1 = dist[n];
    while (!q.empty()) q.pop();
    memset(vis, false, sizeof(vis));
    memset(dist, -1, sizeof(dist));
    queue<node> q;
    for (int i = 1; i <= n; i++) {
      if (!link[1][i]) {
        node d{i, 1};
        vis[1][i] = true;
        dist[i] = 1;
        q.push(d);
      }
    }
    while (!q.empty()) {
      node cur = q.front();
      q.pop();
      for (int i = 1; i <= n; i++) {
        node t = cur;
        if (!link[cur.u][i] && !vis[cur.u][i]) {
          vis[cur.u][i] = true;
          if (dist[i] == -1)
            dist[i] = cur.deep + 1;
          else
            dist[i] = min(dist[i], cur.deep + 1);
          t.u = i;
          t.deep++;
          q.push(t);
        }
      }
    }
    if (dist[n] == -1) {
      vaild = false;
    } else {
      ans2 = dist[n];
    }
  }
  if (vaild) {
    cout << max(ans1, ans2);
  } else {
    cout << "-1";
  }
  cout << endl;
  return 0;
}
