/**
* 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;
}
