#include "bits/stdc++.h"
#define int long long
#define pb push_back
using namespace std;
const int inf = 1e9*2;
const int N = 2e5 + 20;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin>>n>>m;
vector<int> adj[n], a(n);
for(int i = 0; i < n; i++){
cin>>a[i];
}
for(int i = 0; i < m; i++){
int u, v;
cin>>u>>v;
u--, v--;
adj[u].pb(v);
adj[v].pb(u);
}
vector<int> dis1(n, inf), vis(n);
dis1[0] = 0;
priority_queue<pair<int, int> > pq;
pq.push({0, 0});
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
if(vis[node]) continue;
vis[node] = 1;
for(auto itr: adj[node]){
if(dis1[itr] > max(dis1[node] + 1, a[itr])){
dis1[itr] = max(dis1[node] + 1, a[itr]);
pq.push({-dis1[itr], itr});
}
}
}
vector<int> disn(n, inf);
for(int i = 0; i < n; i++){
vis[i] = 0;
}
disn[n-1] = 0;
pq.push({0, n-1});
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
if(vis[node]) continue;
vis[node] = 1;
for(auto itr: adj[node]){
if(disn[itr] > max(disn[node] + 1, a[itr])){
disn[itr] = max(disn[node] + 1, a[itr]);
pq.push({-disn[itr], itr});
}
}
}
int ans = inf;
if(dis1[n-1] == 1){
cout<<1<<endl;
return 0;
}
for(int i = 0; i < n; i++){
ans = min(ans, max(dis1[i], disn[i]) * 2);
}
for(int i = 0; i < n; i++){
for(auto itr: adj[i]){
int val = max(dis1[i], disn[itr]) * 2 + 1;
ans = min(ans, val);
}
}
cout<<ans<<endl;
return 0;
}
/*
11 12
0 0 0 0 0 0 2 2 1 5 0
1 2
2 3
3 4
4 5
5 6
6 11
1 7
7 8
8 9
9 11
1 10
10 11
*/
