#include <bits/stdc++.h>
using namespace std;
const int maxn = 1E3 + 5;
const int ONF = -0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
bool qwe[maxn][maxn];
bool vis[maxn];
int d[maxn];
int n, m;
int Dijkstra(int start) {
  int minpos, tmp;
  memset(vis, false, sizeof(vis));
  memset(d, INF, sizeof(d));
  d[start] = 0;
  for (int i = 1; i <= n; i++) {
    minpos = -1;
    for (int j = 1; j <= n; j++) {
      if (!vis[j])
        if (minpos == -1 || d[j] < d[minpos]) minpos = j;
    }
    if (d[minpos] == INF) break;
    vis[minpos] = true;
    for (int j = 1; j <= n; j++) {
      if (qwe[minpos][j] == true) d[j] = min(d[j], d[minpos] + 1);
    }
  }
  return d[n];
}
int main() {
  int a, b;
  int rail, road;
  while (~scanf("%d%d", &n, &m)) {
    memset(qwe, false, sizeof(qwe));
    for (int i = 1; i <= m; i++) {
      scanf("%d%d", &a, &b);
      qwe[a][b] = true;
      qwe[b][a] = true;
    }
    rail = Dijkstra(1);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (qwe[i][j] == true)
          qwe[i][j] = false;
        else if (qwe[i][j] == false)
          qwe[i][j] = true;
      }
    road = Dijkstra(1);
    if (road == INF || rail == INF)
      printf("-1\n");
    else
      printf("%d\n", max(road, rail));
  }
  return 0;
}
