#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 10;
vector<int> adj[MAXN];
int v[MAXN];
int n, m;
vector<int> calc(int s) {
vector<int> r(n + 1, INF);
vector<int> ok(n + 1);
r[s] = 0;
priority_queue<pii> pq;
pq.push({0, s});
while (!pq.empty()) {
int u = pq.top().se;
pq.pop();
if (ok[u]) continue;
ok[u] = 1;
for (auto to : adj[u]) {
int newD = max(v[to], r[u] + 1);
if (r[to] > newD) {
r[to] = newD;
pq.push({-r[to], to});
}
}
}
return r;
}
int32_t main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> r1 = calc(1), rn = calc(n);
int ans = INF;
for (int i = 1; i <= n; i++) {
for (auto u : adj[i]) ans = min(ans, r1[i] + rn[u] + max(1LL, abs(r1[i] - rn[u])));
}
cout << ans << "\n";
}
