#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e18
using namespace std;
typedef long long ll;
vector<int>adj[200005];
ll h[200005], d[200005], dd[200005];
bool visited[200005];
void solve()
{
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++) { d[i] = INF; dd[i] = INF; }
using T = pair<ll, int>;
priority_queue<T, vector<T>, greater<T>>pq;
d[1] = 0;
pq.push({ 0, 1 });
while (pq.size()) {
int a = pq.top().second; pq.pop();
if (visited[a]) continue;
visited[a] = true;
for (auto u : adj[a]) {
if (d[u] > max(h[u], d[a] + 1)) {
d[u] = max(h[u], d[a] + 1);
pq.push({ d[u], u });
}
}
}
dd[n] = 0;
pq.push({ 0, n });
for (int i = 1; i <= n; i++) visited[i] = false;
while (pq.size()) {
int a = pq.top().second; pq.pop();
if (visited[a]) continue;
visited[a] = true;
for (auto u : adj[a]) {
if (dd[u] > max(h[u], dd[a] + 1)) {
dd[u] = max(h[u], dd[a] + 1);
pq.push({ dd[u], u });
}
}
}
ll ans = INF;
for (int i = 1; i <= n; i++) {
if (d[i] == dd[i])ans = min(ans, d[i] + dd[i]);
for (auto u : adj[i]) {
if (d[i] == dd[u])ans = min(ans, d[i] + dd[u] + 1);
}
}
cout << ans << "\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;// cin>>t;
while (t--) solve();
return 0;
}
