#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second
void solution();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solution();
return 0;
}
#define arr array<ll, 4>
const int N = 2e5+10;
vi adj[N];
ll a[N];
ll n;
void dijkstra(int u, vi &dist) {
vector<bool> vis(n+1);
dist.resize(n+1, 1e18);
priority_queue<pr> q;
q.push({0, u});
dist[u] = 0;
while (!q.empty()) {
auto [d, x] = q.top(); q.pop();
if (vis[x]) continue;
vis[x] = true;
dist[x] = -d;
for (auto y : adj[x]) {
ll val = max(a[y], -(d-1));
q.push({-val, y});
}
}
}
void solution() {
ll m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pr> edge;
while (m--) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
edge.push_back({u, v});
}
vi d1;
vi d2;
dijkstra(1, d1);
dijkstra(n, d2);
ll ans = 1e18;
for (int i = 2; i < n; i++) {
ans = min(ans, 2*max(d1[i], d2[i]));
}
for (auto [x, y] : edge) {
ans = min(ans, 2*max(d1[x], d2[y])+1);
ans = min(ans, 2*max(d1[y], d2[x])+1);
}
cout << ans << endl;
}
