#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (ll)4e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin >> n >> m)) return 0; vector<ll> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector<vector<int>> adj(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u); } vector<ll> d(n, INF); vector<ll> ht(n, 0) ; priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq; d[0] = 0; pq.emplace(0, 0); while (!pq.empty()) { auto [dt, u] = pq.top(); pq.pop(); if (dt != d[u]) continue; for (int v : adj[u]) { // earliest time we can be at v = either move immediately (d[u] + 1), // or wait (raise altitude) until we satisfy a[v] ll nd = max(d[u] + 1, a[v]); if (nd < d[v]) { d[v] = nd; pq.emplace(nd, v); if(a[v]>=d[u]+1) ht[v] = a[v] ; else ht[v] = max(0ll, ht[u]-1) ; } } } cout<<d[n-1]+ht[n-1]<<endl; return 0; }