#include <bits/stdc++.h> using namespace std; #define ll long long #define FOR(i, l, r) for(int i = l; i <= r; i++) #define FORD(i, l, r) for(int i = l; i >= r; i--) #define db double #define ldb long double #define all_1(x) (x).begin(), (x).end() #define all(x) (x).begin(), (x).end() #define ins insert #define pb push_back const int N = 2e5 + 5; int n, m; ll a[N]; vector<int> adj[N]; vector<ll> dijkstra(int source){ vector<ll> dist(n + 1, 2e18); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, source}); dist[source] = 0; while(!pq.empty()){ auto [dist_u, u] = pq.top(); pq.pop(); if(dist_u != dist[u]) continue; for(int v : adj[u]){ ll cand = max(dist[u] + 1, a[v]); if (dist[v] > cand) { dist[v] = cand; pq.push({dist[v], v}); } } } return dist; } void solve(){ cin >> n >> m; FOR(i, 1, n) cin >> a[i]; FOR(i, 1, m){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } vector<ll> dist1 = dijkstra(1); vector<ll> dist2 = dijkstra(n); //dist1: 1 -> i, dist2: n -> i ll ans = 2e18; FOR(i, 1, n){ ans = min(ans, 2ll * max(dist1[i], dist2[i])); } FOR(u, 1, n){ for(int v : adj[u]){ ans = min(ans, 2ll * max(dist1[u], dist2[v]) + 1); } } cout << ans << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }