#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx = 2e5+5, inf = 1e18;
ll n,m,a[nx],dist1[nx],dist2[nx];
vector<int> adj[nx];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= m; i++)
{
ll u,v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= n; i++) dist1[i] = dist2[i] = inf;
dist1[1] = 0;
pq.push({0,1});
while(!pq.empty())
{
auto [d,u] = pq.top();
pq.pop();
if(d > dist1[u]) continue;
for(auto v : adj[u])
{
if(max(d+1,a[v]) < dist1[v])
{
dist1[v] = max(d+1,a[v]);
pq.push({dist1[v],v});
}
}
}
dist2[n] = 0;
pq.push({0,n});
while(!pq.empty())
{
auto [d,u] = pq.top();
pq.pop();
if(d > dist2[u]) continue;
for(auto v : adj[u])
{
if(max(d+1,a[v]) < dist2[v])
{
dist2[v] = max(d+1,a[v]);
pq.push({dist2[v],v});
}
}
}
ll res = 1e18;
for(int i = 1; i <= n; i++)
{
res = min(res, 2*max(dist1[i],dist2[i]));
for(auto v : adj[i]) res = min(res, 2*max(dist1[i],dist2[v])+1);
}
cout<<res;
}
