#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5, inf=1e9;
int n, m, u, v, h[nx], mn[nx], mnr[nx], res=inf;
vector<int> adj[nx];
vector<pair<int ,int>> edg;
priority_queue<pair<int ,int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n; i++) cin>>h[i];
for (int i=1; i<=m; i++) cin>>u>>v, adj[u].push_back(v), adj[v].push_back(u), edg.push_back({u, v}), edg.push_back({v, u});
pq.push({0, 1});
for (int i=2 ;i<=n; i++) mn[i]=inf;
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (cw>mn[u]) continue;
for (auto v:adj[u]) if (mn[v]>max(h[v], mn[u]+1)) mn[v]=max(h[v], mn[u]+1), pq.push({mn[v], v});
}
pq.push({0, n});
for (int i=1; i<n; i++) mnr[i]=inf;
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (cw>mnr[u]) continue;
for (auto v:adj[u]) if (mnr[v]>max(h[v], mnr[u]+1)) mnr[v]=max(h[v], mnr[u]+1), pq.push({mnr[v], v});
}
// for (int i=1; i<=n; i++) cout<<"debug "<<i<<' '<<mn[i]<<' '<<mnr[i]<<'\n';
for (int i=1; i<=n; i++) res=min(res, 2*max(mn[i], mnr[i]));
for (auto [u, v]:edg) if (mn[u]==mnr[v]) res=min(res, mn[u]+mnr[v]+1);
cout<<res;
}
