// File airplane.cpp created on 24.10.2025 at 11:21:49
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int inf = int(1E9);
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
int U, V;
std::cin >> U >> V;
--U, --V;
adj[U].emplace_back(V);
adj[V].emplace_back(U);
}
min_pq<std::pair<int, int>> pq;
std::vector<int> dis0(N, inf);
pq.emplace(dis0[0] = 0, 0);
while (!pq.empty()) {
auto[d, v] = pq.top();
pq.pop();
if (d != dis0[v]) {
continue;
}
for (auto u : adj[v]) {
if (chmin(dis0[u], std::max(d + 1, A[u]))) {
pq.emplace(dis0[u], u);
}
}
}
std::vector<int> disN(N, inf);
pq.emplace(disN[N - 1] = 0, N - 1);
while (!pq.empty()) {
auto[d, v] = pq.top();
pq.pop();
if (d != disN[v]) {
continue;
}
for (auto u : adj[v]) {
if (chmin(disN[u], std::max(d + 1, A[u]))) {
pq.emplace(disN[u], u);
}
}
}
debug(dis0, disN);
int ans = inf;
for (int v = 0; v < N; ++v) {
ans = std::min(ans, std::max(dis0[v], disN[v]) * 2);
for (auto u : adj[v]) {
ans = std::min(ans, std::max(dis0[v], disN[u]) * 2 + 1);
}
}
std::cout << ans << '\n';
return 0;
}
