#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>
ll n, m,k, t;
ll h[dim];
vll a[dim];
ll mn1[dim], mnn[dim];
void dey(ll st, ll *dst){
dst[st]=0;
set<pll> s;
while(s.size()>0){
ll v=(*s.begin()).se;
for(auto x:a[v]){
ll w=max<ll>(dst[v],h[x]);
if(dst[x]>w){
s.erase({ dst[x], x});
dst[x]=w;
s.insert({dst[x], x});
}
}
}
}
int main() {
ll u,v, w, q, l, r;
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>h[i];
mn1[i]=inf;
mnn[i]=inf;
}
for(int i=1; i<=m; i++){
cin>>u>>v;
a[u].pb(v);
a[v].pb(u);
}
mn1[1]=0;
set<pll> s;
s.insert({0, 1});
while(s.size()>0){
ll v=(*s.begin()).se;
s.erase(s.begin());
for(auto x:a[v]){
ll w=max<ll>(mn1[v]+1,h[x]);
if(mn1[x]>w){
s.erase({ mn1[x], x});
mn1[x]=w;
s.insert({mn1[x], x});
}
}
}
mnn[n]=0;
s.insert({0, n});
while(s.size()>0){
ll v=(*s.begin()).se;
s.erase(s.begin());
for(auto x:a[v]){
ll w=max<ll>(mnn[v]+1,h[x]);
if(mnn[x]>w){
s.erase({ mnn[x], x});
mnn[x]=w;
s.insert({mnn[x], x});
}
}
}
/* for(int i=1; i<=n; i++){
cout<<mn1[i]<<" ";
}
cout<<endl;
for(int i=1; i<=n; i++){
cout<<mnn[i]<<" ";
}*/
ll ans=inf;
for(int i=1; i<=n; i++){
if(mn1[i]>=mnn[i])ans=min(ans, 2*mn1[i]);
for(auto x: a[i]){
if(mn1[i]>=mnn[x]){
ans=min(ans, 2*mn1[i]+1);
}
}
}
cout<<ans<<endl;
return 0;
}
