#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=2e5+5; int n, m, a[nx], d[nx][2], ans=inf; vector<int> adj[nx]; struct dak { int v, w; bool operator <(const dak &o) const { return w>o.w; } }; priority_queue<dak> f; void dich(int s, int k) { d[s][k]=0; f.push({s, 0}); while(f.size()) { dak v=f.top(); f.pop(); if(d[v.v][k]<v.w) continue; for(int u:adj[v.v]) { int nxt=max(a[u], d[v.v][k]+1); if(d[u][k]>nxt) d[u][k]=nxt, f.push({u, d[u][k]}); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i = 1; i <= n; i++) cin>>a[i]; while(m--) { int u, v; cin>>u>>v; adj[u].emplace_back(v); adj[v].emplace_back(u); } memset(d, 0x3f, sizeof(d)); dich(1, 0); dich(n, 1); for(int i = 1; i <= n; i++) ans=min(ans, 2*max(d[i][0], d[i][1])); for(int u = 1; u <= n; u++) for(int v:adj[u]) ans=min(ans, 2*max(d[u][0], d[v][1])+1); cout<<ans; }