#include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 2 * 1e5 + 1; vector<int> g[maxn]; int n ,m; vector<int> d1 , d2; int a[maxn]; vector<int> compute(int u){ priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int ,int>>> pq; pq.push({0 , u}); vector<int> dist(n + 1 , LLONG_MAX/4); dist[u] = 0; while(!pq.empty()){ int d = pq.top().first; int u = pq.top().second; pq.pop(); if(dist[u] != d)continue; for(auto v : g[u]){ int nd = max(d + 1 , a[v]); if(dist[v] > nd){ dist[v] = nd; pq.emplace(nd , v); } } } return dist; } signed main(){ cin>>n>>m; for(int i =1;i<=n;i++)cin>>a[i]; for(int i = 0 ;i < m ;i++){ int u , v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } d1 = compute(1); d2 = compute(n); int ans = LLONG_MAX/4; for(int i = 1 ; i <= n ; i++){ if(d1[i] == LLONG_MAX/4 || d2[i] == LLONG_MAX/4)continue; int cand = 2 * max(d1[i] , d2[i]); ans = min(cand , ans); } for(int u = 1 ; u <= n ; u++){ for(int v : g[u]){ if(d1[u] == LLONG_MAX/4 || d2[v] == LLONG_MAX/4)continue; int cand = 2 * max(d1[u] , d2[v]) + 1; ans = min(ans , cand); } } cout<<ans; }