#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int n, m, a[nx], u, v, mn[nx], mnr[nx], vs[nx], res=1e9;
vector<int> d[nx];
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>>a[i], mn[i]=mnr[i]=1e9;
for (int i=1; i<=m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
mn[1]=mnr[n]=0;
pq.push({0, 1});
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (auto v:d[u]) if (mn[v]>max(cw+1, a[v])) mn[v]=max(cw+1, a[v]), pq.push({mn[v], v});
}
pq.push({0, n});
for (int i=1; i<=n; i++) vs[i]=0;
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (auto v:d[u]) if (mnr[v]>max(cw+1, a[v])) mnr[v]=max(cw+1, a[v]), pq.push({mnr[v], v});
}
for (int i=1; i<=n; i++) res=min(res, 2*max(mn[i], mnr[i]));
for (int u=1; u<=n; u++) for (auto v:d[u]) res=min(res, 2*max(mn[u], mnr[v])+1);
cout<<res;
}
