#include<bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
const int N=2e5+5,INF=1e18;
int n,m,a[N],d1[N],d2[N],ans=INF;
vector<int>adj[N];
void f(int st,int*dist){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
fill(dist,dist+n+1,INF),dist[st]=0;pq.emplace(0,st);
while(pq.size()){
auto[d,u]=pq.top();pq.pop();
if(d<=dist[u])for(auto v:adj[u])if(max(d+1,a[v])<dist[v])dist[v]=max(d+1,a[v]),pq.emplace(max(d+1,a[v]),v);
}
}
signed main(void){
exoworldgd;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0,u,v;i<m;i++)cin>>u>>v,adj[u].emplace_back(v),adj[v].emplace_back(u);
f(1,d1),f(n,d2);
for(int i=1;i<=n;i++)ans=min(ans,max(d1[i],d2[i])*2);
for(int u=1;u<=n;u++)for(auto v:adj[u])ans=min(ans,max(d1[u],d2[v])*2+1);
cout<<ans;
}
