#include <bits/stdc++.h>

constexpr int INF = std::numeric_limits<int>::max() / 2;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::istream &fin = std::cin;
  std::ostream &fout = std::cout;
  
  int n, m;
  fin >> n >> m;

  std::vector<int> a(n);

  for (int i = 0; i < n; ++i) {
    fin >> a[i];
  }

  std::vector<std::vector<int>> adj(n);

  for (int i = 0; i < m; ++i) {
    int u, v;
    fin >> u >> v;
    --u;
    --v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  auto dijkstra = [&](int s) {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> que;
    std::vector<int> dis(n, INF);
    que.emplace(dis[s] = 0, s);

    while (!que.empty()) {
      auto [d, u] = que.top();
      que.pop();

      if (d > dis[u]) {
        continue;
      }

      for (auto v : adj[u]) {
        if (std::max(d + 1, a[v]) < dis[v]) {
          dis[v] = std::max(d + 1, a[v]);
          que.emplace(dis[v], v);
        }
      }
    }

    return dis;
  };

  auto f = dijkstra(0), g = dijkstra(n - 1);
  int res = INF;

  for (int i = 0; i < n; ++i) {
    if (f[i] == g[i]) {
      res = std::min(res, f[i] * 2);
    } else {
      for (int j : adj[i]) {
        if (f[i] == g[j]) {
          res = std::min(res, f[i] * 2 + 1);
          break;
        }
      }
    }
  }

  fout << res << '\n';
}