#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep2(i, n, m) for (int i = (n); i < (m); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr(i, n) for (int i = n; i--;)
using vi = vector<int>;

void ints(auto& ...ints) { (scanf("%d", &ints), ...); }

constexpr int MaxN = 200'006;
vi G[MaxN];
int n, m;
int par[19][MaxN];
vi ch[MaxN];
int dist[MaxN];
int ord[MaxN], out[MaxN], dep[MaxN];
int seg[MaxN*2];
pair<int, int> es[MaxN];
map<pair<int, int>, vi> mp;
int F[MaxN];
ll dp[MaxN];

void upd(int i, int x) {
  i += MaxN;
  seg[i] = min(seg[i], x);
  for (i = i / 2; i; i /= 2) {
    seg[i] = min(seg[i*2], seg[i*2+1]);
  }
}
int query(int l, int r) {
  int ans = INT_MAX;
  for (l += MaxN, r += MaxN; l < r; l /= 2, r /= 2) {
    if (l % 2) ans = min(ans, seg[l++]);
    if (r % 2) ans = min(ans, seg[--r]);
  }
  return ans;
}

int par_by(int v, int k) {
  rep(i, size(par)) if (k >> i & 1) v = v == -1 ? -1 : par[i][v];
  return v;
}

int lca(int u, int v) {
  if (dist[u] > dist[v]) swap(u, v);
  v = par_by(v, dist[v] - dist[u]);
  if (u == v) return v;
  repr(i, size(par)) if (par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
  return par[0][u];
}

void dfs(int v) {
  static int t = 0;
  ord[v] = t++;
  for (int u : ch[v]) {
    dfs(u);
  }
  out[v] = t;
  // cerr << v << ' ' << ord[v] <<' ' << out[v] << endl;
}

void dfs2(int v) {
  if (par[0][v] == -1) F[v] = 0;
  else F[v] = query(ord[v], out[v]) - dist[v] + 1;

  for (int u : ch[v]) {
    if (mp.count(pair(u, v))) for (int i : mp[pair(u, v)]) {
      auto [a, b] = es[i];
      // cerr << a << ' ' << ord[a] << ' ' << dist[a] << ' ' << dist[b] << endl;
      upd(ord[a], dist[a] + dist[b]);
    }
    dfs2(u);
  }
}

int main() {
  ints(n, m);
  rep(i, m) {
    int u, v;
    ints(u, v), u--, v--;
    es[i] = pair(u, v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  fill(dist, dist+n, INT_MAX / 2);
  dist[n-1] = 0;
  par[0][n-1] = -1;
  queue<int> nxt;
  nxt.push(n-1);
  while (!nxt.empty()) {
    int v = nxt.front();
    nxt.pop();
    for (int u : G[v]) if (dist[u] > dist[v] + 1) {
      dist[u] = dist[v] + 1;
      par[0][u] = v;
      nxt.push(u);
    }
  }
  rep(t, size(par)-1) rep(v, n) par[t+1][v] = par[t][v] == -1 ? -1 : par[t][par[t][v]];

  rep(i, m) {
    auto [u, v] = es[i];
    if (dist[u] > dist[v]) swap(u, v);
    if (dist[u] + 1 == dist[v] && par[0][u] == v) continue;
    int a = lca(u, v);
    if (u != a) mp[pair(par_by(u, dist[u] - dist[a] - 1), a)].push_back(i);
    if (v != a) mp[pair(par_by(v, dist[v] - dist[a] - 1), a)].push_back(i);
  }

  rep(v, n) if (par[0][v] != -1) ch[par[0][v]].push_back(v);

  dfs(n-1);

  dfs2(n-1);

  // rep(i, n) cerr << F[i] << ' ';
  // cerr << endl;

  fill(dp, dp+n, LLONG_MAX / 2);
  dp[n-1] = 0;
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
  pq.emplace(0, n-1);
  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    if (d != dp[v]) continue;
    for (int u : G[v]) {
      auto d2 = d + F[v] + 1;
      if (dp[u] > d2) pq.emplace(dp[u] = d2, u);
    }
  }

  printf("%lld\n", dp[0] + F[0] + dist[0]);
}