#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 2e5 + 5;
vector<int> g[N];
int n, m, a[N], D[N][2], ans = 1e9;
void shortest_path(int s, int t) {
for(int i=1; i<=n; i++) D[i][t] = 1e9;
priority_queue<pii, vector<pii>, greater<> > pq;
pq.push({ D[s][t] = 0, s });
while(!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if(d != D[u][t]) continue;
for(int v : g[u]) {
int w = max(d + 1, a[v]);
if(D[v][t] > w) pq.push({ D[v][t] = w, v });
}
}
}
signed main() {
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
while(m--) {
int a, b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
shortest_path(1, 0);
shortest_path(n, 1);
for(int u=1; u<=n; u++) {
ans = min(ans, 2 * max(D[u][0], D[u][1]));
for(int v : g[u])
for(int i : { 0, 1 })
ans = min(ans, 2 * max(D[u][i], D[v][i^1]) + 1);
}
cout << ans << '\n';
}
