#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2 * 1e5 + 1;
vector<int> g[maxn];
int n ,m;
vector<int> d1 , d2;
int a[maxn];
vector<int> compute(int u){
priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int ,int>>> pq;
pq.push({0 , u});
vector<int> dist(n + 1 , LLONG_MAX/4);
dist[u] = 0;
while(!pq.empty()){
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if(dist[u] != d)continue;
for(auto v : g[u]){
int nd = max(d + 1 , a[v]);
if(dist[v] > nd){
dist[v] = nd;
pq.emplace(nd , v);
}
}
}
return dist;
}
signed main(){
cin>>n>>m;
for(int i =1;i<=n;i++)cin>>a[i];
for(int i = 0 ;i < m ;i++){
int u , v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
d1 = compute(1);
d2 = compute(n);
int ans = LLONG_MAX/4;
for(int i = 1 ; i <= n ; i++){
if(d1[i] == LLONG_MAX/4 || d2[i] == LLONG_MAX/4)continue;
int cand = 2 * max(d1[i] , d2[i]);
ans = min(cand , ans);
}
for(int u = 1 ; u <= n ; u++){
for(int v : g[u]){
if(d1[u] == LLONG_MAX/4 || d2[v] == LLONG_MAX/4)continue;
int cand = 2 * max(d1[u] , d2[v]) + 1;
ans = min(ans , cand);
}
}
cout<<ans;
}
