#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <tuple>
int gs, edg;
std::vector<int> node_altitude;
std::vector<std::vector<int>> adj_list;
void build_graph() {
std::cin >> gs >> edg;
node_altitude.resize(gs+1);
adj_list.resize(gs+1);
for (int i = 1; i <= gs; i++) {
std::cin >> node_altitude[i];
}
for (int i = 0, a, b; i < edg; i++) {
std::cin >> a >> b;
adj_list[a].emplace_back(b);
adj_list[b].emplace_back(a);
}
}
bool can_improve(std::unordered_map<int,int>& map, int pos, int val) {
if (!map.count(pos)) {
return 1;
}
return map[pos] > val;
}
void shortest_path() {
std::vector<std::unordered_map<int,int>> dist(gs+1);
std::priority_queue<std::tuple<int,int,int>, std::vector<std::tuple<int,int,int>>, std::greater<std::tuple<int,int,int>>> pq;
pq.emplace(0,1,0);
dist[1][0] = 0;
while (!pq.empty()) {
auto [c, k, h] = pq.top();
pq.pop();
for (const auto& i : adj_list[k]) {
if (node_altitude[i] <= h) {
if (can_improve(dist[i],h,dist[k][h]+1)) {
dist[i][h] = dist[k][h]+1;
pq.emplace(dist[i][h],i,h);
}
}
if (node_altitude[i] >= h) {
if (can_improve(dist[i],node_altitude[i],dist[k][h]+std::max(0,node_altitude[i]-h-1)+1)) {
dist[i][node_altitude[i]] = dist[k][h] + std::max(0, node_altitude[i]-h-1) + 1;
pq.emplace(dist[i][node_altitude[i]], i, node_altitude[i]);
}
}
if (node_altitude[i] < h) {
if (h-1 >= 0 && can_improve(dist[i],h-1,dist[k][h]+1)) {
dist[i][h-1] = dist[k][h]+1;
pq.emplace(dist[i][h-1],i,h-1);
}
}
}
}
int ret = 0x7f7f7f7f;
for (const auto& i : dist[gs]) {
ret = std::min(ret, i.second + i.first);
}
std::cout << ret << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
build_graph();
shortest_path();
}
