#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; }