#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
int n, m;
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
vector<int> adj[n];
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
priority_queue<array<int, 3>, vector<array<int, 3> >, greater<array<int, 3> > > pq;
pq.push({0, 0, 0});
bool vis[2005][2005];
memset(vis, 0, sizeof(vis));
long long ans = 0;
while(!pq.empty()){
array<int, 3> cur = pq.top();
pq.pop();
if(cur[1] > 2000) continue;
if(cur[1] == 0 && cur[2] == n - 1){
ans = cur[0];
break;
}
if(vis[cur[1]][cur[2]]) continue;
vis[cur[1]][cur[2]] = 1;
if(!vis[cur[1] + 1][cur[2]]) pq.push({cur[0] + 1, cur[1] + 1, cur[2]});
if(cur[1] > a[cur[2]] && !vis[cur[1] - 1][cur[2]]) pq.push({cur[0] + 1, cur[1] - 1, cur[2]});
for(int i : adj[cur[2]]){
if(cur[1] - 1 >= a[i] && !vis[cur[1] - 1][i]) pq.push({cur[0] + 1, cur[1] - 1, i});
if(cur[1] >= a[i] && !vis[cur[1]][i]) pq.push({cur[0] + 1, cur[1], i});
if(cur[1] + 1 >= a[i] && !vis[cur[1] + 1][i]) pq.push({cur[0] + 1,cur[1] + 1, i});
}
}
cout << ans << '\n';
}
