#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
int n, m, a[nx], d[nx][2], ans=inf;
vector<int> adj[nx];
struct dak
{
int v, w;
bool operator <(const dak &o)
const
{
return w>o.w;
}
};
priority_queue<dak> f;
void dich(int s, int k)
{
d[s][k]=0;
f.push({s, 0});
while(f.size())
{
dak v=f.top();
f.pop();
if(d[v.v][k]<v.w) continue;
for(int u:adj[v.v])
{
int nxt=max(a[u], d[v.v][k]+1);
if(d[u][k]>nxt)
d[u][k]=nxt, f.push({u, d[u][k]});
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++)
cin>>a[i];
while(m--)
{
int u, v;
cin>>u>>v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
memset(d, 0x3f, sizeof(d));
dich(1, 0);
dich(n, 1);
for(int i = 1; i <= n; i++)
ans=min(ans, 2*max(d[i][0], d[i][1]));
for(int u = 1; u <= n; u++)
for(int v:adj[u])
ans=min(ans, 2*max(d[u][0], d[v][1])+1);
cout<<ans;
}
