#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e16;
struct min_height {
int d, h, u;
min_height (int _d, int _h, int _u) : d(_d), h(_h), u(_u) {}
bool operator < (const min_height &oth) const {
return (d < oth.d || (d == oth.d && h < oth.h));
}
bool operator > (const min_height &oth) const {
return (d > oth.d || (d == oth.d && h > oth.h));
}
};
struct max_height {
int d, h, u;
max_height (int _d, int _h, int _u) : d(_d), h(_h), u(_u) {}
bool operator < (const max_height &oth) const {
return (d < oth.d || (d == oth.d && h > oth.h));
}
bool operator > (const max_height &oth) const {
return (d > oth.d || (d == oth.d && h < oth.h));
}
};
const int N = 200200;
int n, m, a[N];
pair<int, int> f1[N][2], f2[N][2];
vector<int> adj[N];
bool intersect (int l, int r, int u, int v){
if (v >= l && r >= v){
return true;
}
if (u >= l && r >= u){
return true;
}
if (l >= u && l <= v){
return true;
}
if (r >= u && r <= v){
return true;
}
return false;
}
int32_t main (){
ios::sync_with_stdio(false); cin.tie(nullptr);
if (fopen("test.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> a[i];
f1[i][0] = f1[i][1] = {inf, inf};
f2[i][0] = f2[i][1] = {inf, -1};
}
for (int i = 1; i <= m; ++i){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// solve for f1
if (true){
priority_queue<min_height, vector<min_height>, greater<min_height>> pq;
// solve for 1
f1[1][0] = {0, 0}; pq.push(min_height(0, 0, 1));
while (pq.size()){
auto [d, h, u] = pq.top(); pq.pop();
auto [X, Y] = f1[u][0];
if (X < d || (X == d && Y < h)){
continue;
}
for (int v : adj[u]){
int nd = max(d + 1, a[v]);
int nh = (h > a[v] ? h - 1 : a[v]);
auto [X, Y] = f1[v][0];
if (X > nd || (X == nd && Y > nh)){
f1[v][0] = {nd, nh};
pq.push(min_height(nd, nh, v));
}
}
}
// solve for n
f1[n][1] = {0, 0}; pq.push(min_height(0, 0, n));
while (pq.size()){
auto [d, h, u] = pq.top(); pq.pop();
auto [X, Y] = f1[u][1];
if (X < d || (X == d && Y < h)){
continue;
}
for (int v : adj[u]){
int nd = max(d + 1, a[v]);
int nh = (h > a[v] ? h - 1 : a[v]);
auto [X, Y] = f1[v][1];
if (X > nd || (X == nd && Y > nh)){
f1[v][1] = {nd, nh};
pq.push(min_height(nd, nh, v));
}
}
}
}
// solve for f2
if (true){
priority_queue<max_height, vector<max_height>, greater<max_height>> pq;
// solve for 1
f2[1][0] = {0, 0}; pq.push(max_height(0, 0, 1));
while (pq.size()){
auto [d, h, u] = pq.top(); pq.pop();
auto [X, Y] = f2[u][0];
if (X < d || (X == d && Y > h)){
continue;
}
for (int v : adj[u]){
int nd = max(d + 1, a[v]);
int nh = max(h + 1, a[v]);
auto [X, Y] = f2[v][0];
if (X > nd || (X == nd && Y < nh)){
f2[v][0] = {nd, nh};
pq.push(max_height(nd, nh, v));
}
}
}
// solve for n
f2[n][1] = {0, 0}; pq.push(max_height(0, 0, n));
while (pq.size()){
auto [d, h, u] = pq.top(); pq.pop();
auto [X, Y] = f2[u][1];
if (X < d || (X == d && Y > h)){
continue;
}
for (int v : adj[u]){
int nd = max(d + 1, a[v]);
int nh = max(h + 1, a[v]);
auto [X, Y] = f2[v][1];
if (X > nd || (X == nd && Y < nh)){
f2[v][1] = {nd, nh};
pq.push(max_height(nd, nh, v));
}
}
}
}
int ans = inf;
for (int i = 1; i <= n; ++i){
int d1 = f1[i][0].first;
int d2 = f2[i][1].first;
int l = f1[i][0].second, r = f2[i][0].second;
int u = f1[i][1].second, v = f2[i][1].second;
if (intersect(l, r, u, v)){
ans = min(ans, d1 + d2);
} else {
ans = min(ans, d1 + d2 + max(u - r, l - v));
}
}
cout << ans << "\n";
}
