#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int max(int i, int j) { return i > j ? i : j; }
int min(int i, int j) { return i < j ? i : j; }
#define N 200005
const int oo = 1e9;
int n, m, a[N], *eh[N], eo[N], to, dp[N], dq[N], *focus, t[N * 2], z = oo;
int Lt(int i, int j) { return focus[i] < focus[j]; }
int Min(int i, int j) { return Lt(i, j) ? i : j; }
void pul(int i) { t[i] = Min(t[i * 2], t[i * 2 + 1]); }
void fix(int i) { for (i += n; i /= 2; ) pul(i); }
void pus(int i, int j) {
int o = eo[i]++;
if (!o) eh[i] = (int*)malloc(sizeof **eh * 2);
else if (!(o & (o - 1))) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
eh[i][o] = j;
}
void Dijkstra(int src, int *dp) {
focus = dp;
for (int i = 0; i < n; ++i) dp[i] = oo, t[i + n] = i;
dp[src] = 0;
dp[n] = oo + 1;
for (int i = n; --i;) pul(i);
for (int i = 1; i <= n; ++i) {
int u = t[1];
t[u + n] = n;
fix(u);
for (int v, j = 0; j < eo[u]; ++j) {
v = eh[u][j];
int nc = max(dp[u] + 1, a[v]);
if (t[v + n] == v && nc < dp[v]) {
dp[v] = nc;
fix(v);
}
}
}
}
int main() {
srand(time(0));
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%d", a + i);
for (int u, v, i = 0; i < m; ++i)
scanf("%d%d", &u, &v), pus(--u, --v), pus(v, u);
Dijkstra(0, dp);
Dijkstra(n - 1, dq);
for (int i = 0; i < n; ++i) {
z = min(z, max(dp[i], dq[i]) * 2);
for (int k = 0; k < eo[i]; ++k) {
int j = eh[i][k];
z = min(z, 2 * max(dp[i], dq[j]) + 1);
}
}
printf("%d", z);
}
