#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], dist[x]+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, 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; }