#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define fr first #define sc second #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<ll> a(n+1); for (int i = 1; i <= n; ++i) cin >> a[i]; vector<vector<int>> adj(n+1); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } vector<bool> vis(n+1, 0); vector<ll> dist1(n+1, 1e18); dist1[1] = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int v : adj[u]) { ll w = max(dist1[u]+1, a[v]); if (dist1[v] > w) { dist1[v] = w; pq.push({dist1[v], v}); } } } vis.assign(n+1, 0); vector<ll> distn(n+1, 1e18); distn[n] = 0; pq.push({0, n}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int v : adj[u]) { ll w = max(distn[u]+1, a[v]); if (distn[v] > w) { distn[v] = w; pq.push({distn[v], v}); } } } ll ans = 1e18; for (int u = 1; u <= n; ++u) { mnto(ans, max(dist1[u], distn[u])<<1); for (int v : adj[u]) { mnto(ans, max(dist1[u], distn[v])<<1|1); mnto(ans, max(distn[u], dist1[v])<<1|1); } } cout << ans; }