/** * Author: trviet * Studies at: Le Hong Phong High School for the Gifted **/ #include <bits/stdc++.h> using namespace std; constexpr int maxn = 2e5 + 5; vector<int> graph[maxn]; int n, m, a[maxn]; vector<int> dijkstra(int s) { vector<int> dp(n + 5, 1e9); priority_queue<pair<int, int>> pq; dp[s] = 0; pq.push({0, s}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (int v : graph[u]) if (dp[v] > max(a[v], dp[u] + 1)) { dp[v] = max(a[v], dp[u] + 1); pq.push({-dp[v], v}); } } return dp; } void ReadData() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; while (m-- > 0) { int u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } } void Solve() { vector<int> f = dijkstra(1); vector<int> g = dijkstra(n); int ans = 2e9 + 1e8; for (int u = 1; u <= n; ++u) { ans = min(ans, max(f[u], g[u]) * 2); for (int v : graph[u]) ans = min(ans, min(max(f[u], g[v]), max(f[v], g[u])) * 2 + 1); } cout << ans; } int main() { ReadData(); Solve(); return 0; }