#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms (a); memset (a, 0, sizeof a);
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T& a, T b) {
return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T& a, T b) {
return (b > a) ? a = b, 1 : 0;
}
using namespace std;
const int N = 5e5 + 5;
int T, n, m, a[N], d[3][N], ans = 1e18;
vector <int> g[N];
void dij (int t, int s) {
re (i, 1, n, 1) d[t][i] = 1e18;
d[t][s] = 0;
priority_queue <PII, vector <PII>, greater<PII> >pq;
pq.push ({d[t][s], s});
while (! pq.empty ()) {
int x = pq.top ().S;
pq.pop();
for (int v : g[x]) if (d[t][v] > max (d[t][x] + 1, a[v])) {
d[t][v] = max (d[t][x] + 1, a[v]);
pq.push ({d[t][v], v});
}
}
}
signed main () {
cout << fixed << setprecision (0);
ios :: sync_with_stdio (0), cin.tie (0), cout.tie (0);
cin >> n >> m;
int x, y;
re (i, 1, n, 1) cin >> a[i];
re (i, 1, m, 1) cin >> x >> y, g[x].pb (y), g[y].pb (x);
dij (0, 1);
dij (1, n);
re (i, 1, n, 1) if (abs (d[0][i] - d[1][i]) <= 1) chkmin (ans, d[0][i] + d[1][i]);
cout << ans;
return 0;
}
