#include <bits/stdc++.h>
using namespace std;
int wys[200007];
int odl_do_gory[200007];
int odl_do_dolu[200007];
vector<int> graph[200007];
int n;
void djikstraz1()
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, 1});
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
int odlcur = cur.first;
int gdzie = cur.second;
if(odl_do_gory[gdzie] < odlcur)
{
continue;
}
for(auto x : graph[gdzie])
{
if(odl_do_dolu[x] > max(odlcur + 1, wys[x]))
{
odl_do_dolu[x] = max(odlcur + 1, wys[x]);
pq.push({odl_do_dolu[x], x});
}
}
}
}
void djikstrazn(int n)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, n});
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
int odlcur = cur.first;
int gdzie = cur.second;
if(odl_do_gory[gdzie] < odlcur)
{
continue;
}
for(auto x : graph[gdzie])
{
if(odl_do_gory[x] > max(odlcur + 1, wys[x]))
{
odl_do_gory[x] = max(odlcur + 1, wys[x]);
pq.push({odl_do_gory[x], x});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, a, b;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
odl_do_gory[i] = odl_do_dolu[i] = INT_MAX / (int)2;
cin >> wys[i];
}
odl_do_dolu[1] = 0;
odl_do_gory[n] = 0;
for(int i = 0; i < m; i++)
{
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
djikstraz1();
djikstrazn(n);
int wyn = INT_MAX;
for(int i = 1; i <= n; i++)
{
//cout << odl_do_dolu[i] << " " << odl_do_gory[i] << endl;
wyn = min(wyn, 2 * max(odl_do_dolu[i], odl_do_gory[i]));
for(auto x : graph[i])
{
wyn = min(wyn, 2 * max(odl_do_dolu[i], odl_do_gory[x]) + 1);
wyn = min(wyn, 2 * max(odl_do_dolu[x], odl_do_gory[i]) + 1);
}
}
cout << wyn << endl;
return 0;
}
