#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
//[NOISG 2023 Finals] Airplane
ll n, m, mxa;
vector<ll> a;
vector<vector<ll>> dp, adj;
bool chk(ll A, ll B){
if(0<=A && A<n && 0<=B && B<mxa+2) return 1;
return 0;
}
void f() {
cin >> n >> m;
a.resize(n);
for(auto& u : a) cin >> u;
mxa=*max_element(all(a));
dp.assign(n, vector<ll>(mxa+2, -1));
for(ll i=0; i<n; i++){
for(ll j=0; j<a[i]; j++) dp[i][j]=-2;
}
adj.assign(n, vector<ll>(0));
for(ll i=0; i<m; i++){
ll x, y; cin >> x >> y;
x--; y--;
adj[x].pb(y);
adj[y].pb(x);
}
priority_queue<pair<ll, pair<ll, ll>>> q;
q.push({0, {0, 0}});
while(!q.empty()){
ll nw=q.top().fi*(-1);
pair<ll, ll> plc=q.top().se;
q.pop();
if(dp[plc.fi][plc.se]!=-1 && dp[plc.fi][plc.se]<=nw) continue;
dp[plc.fi][plc.se]=nw;
vector<ll> dy={1, -1};
for(int i=0; i<2; i++){
if(chk(plc.fi, plc.se+dy[i])){
if(dp[plc.fi][plc.se+dy[i]]==-2) continue;
if(dp[plc.fi][plc.se+dy[i]]==-1 || dp[plc.fi][plc.se+dy[i]]>nw+1){
q.push({(-1)*(nw+1), {plc.fi, plc.se+dy[i]}});
}
}
}
dy={-1, 0, 1};
for(auto& u : adj[plc.fi]){
for(int i=0; i<3; i++){
if(chk(u, plc.se+dy[i])){
if(dp[u][plc.se+dy[i]]==-2) continue;
if(dp[u][plc.se+dy[i]]==-1 || dp[u][plc.se+dy[i]]>nw+1){
q.push({(-1)*(nw+1), {u, plc.se+dy[i]}});
}
}
}
}
}
cout << dp[n-1][0];
}
int main() {
int tc=1;
// cin >> tc;
for(int i=1; i<=tc; i++){
// cout << '#' << i << endl;
f();
if(i!=tc) cout << endl;
}
}
