#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> const int nx = 2e5+5; const int INF = 1e9; int n, m, a[nx], res = INF; vector<int> adj[nx]; priority_queue<pii, vector<pii>, greater<pii>> pq; vector<int> dist(int n) { vector<int> vs(nx, 0), d(nx, INF); d[n] = 0; pq.push({0, n}); while(!pq.empty()) { auto [cw, u] = pq.top(); pq.pop(); if(vs[u]) continue; vs[u] = 1; for(auto v : adj[u]) { if(d[v] > max(cw + 1, a[v])) { d[v] = max(cw + 1, a[v]); pq.push({d[v], v}); } } } return d; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=m;i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } vector<int> mn = dist(1); vector<int> mnr = dist(n); for(int i=1;i<=n;i++) res = min(res, 2 * max(mn[i], mnr[i])); for(int u=1;u<=n;u++) { for(auto v : adj[u]) res = min(res, 2 * max(mn[u], mnr[v]) + 1); } cout << res ; return 0; }