#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const long long INF=1e18;
long long dp1[MAXN],dp2[MAXN],F[MAXN],A[MAXN];
vector<int> ds[MAXN];
priority_queue< pair<long long,int>,vector< pair<long long,int> >,greater< pair<long long,int> > > pq;
queue<int> Q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>A[i];
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
ds[l].push_back(r),ds[r].push_back(l);
}
for(int i=1;i<=n;i++) dp1[i]=dp2[i]=INF;
dp1[1]=0,pq.push({0,1});
while(!pq.empty())
{
long long a=pq.top().first;
int b=pq.top().second;
pq.pop();
if(dp1[b]<a) continue;
for(auto v:ds[b]) if(dp1[v]>max(a+1,A[v])) pq.push({dp1[v]=max(a+1,A[v]),v});
}
dp2[n]=0,pq.push({0,n});
while(!pq.empty())
{
long long a=pq.top().first;
int b=pq.top().second;
pq.pop();
if(dp2[b]<a) continue;
for(auto v:ds[b]) if(dp2[v]>max(a+1,A[v])) pq.push({dp2[v]=max(a+1,A[v]),v});
}
long long ans=INF;
for(int i=1;i<=n;i++)
{
ans=min(ans,max(dp1[i],dp2[i])*2);
for(auto v:ds[i]) ans=min(ans,max(dp1[i],dp2[v])*2+1);
}
cout<<ans;
}
