#include <bits/stdc++.h>
#define lli long long int
#define MP make_pair
#define REP(i,n) for(int i = 0; (i)<(n); (i)++)
#define pb push_back
const int N = 2e5+5;
const int M = 4e3+5;
const int MOD = 1e9+7;
const int INF = 1e9 + 500;
using namespace std;
void fastio() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
}
int n,m,q;
vector<int> a(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<int> dp1, dp2;
void bfs(int src, vector<int> &sp) {
priority_queue<array<int,2>, vector<array<int,2> >, greater<array<int,2> > > que;
sp.assign(n + 3, INF);
sp[src] = 0;
que.push({0, src});
while(que.size()) {
auto cur = que.top();
que.pop();
for(auto c : adj[cur[1]]) {
if(sp[c] != INF) continue;
sp[c] = max(cur[0] + 1 , a[c]);
que.push({sp[c], c});
}
}
}
void solve() {
cin>>n>>m;
REP(i,n) cin>>a[i + 1];
for(int i = 1; i<=m; i++) {
int u,v;
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
int ans = INF;
bfs(1, dp1);
bfs(n, dp2);
for(int i = 1; i<=n; i++) {
int ret = max(dp1[i] , dp2[i]) * 2;
ans = min(ans , ret);
}
for(int i = 1; i<=n; i++) {
for(auto c : adj[i]) {
if(dp1[i] == dp2[c]) ans = min(ans, dp1[i] * 2 + 1);
}
}
cout<<ans<<"\n";
}
signed main() {
fastio();
solve();
}
