#include "bits/stdc++.h"
using namespace std;

#define int long long
#define fr first
#define sc second
#define eb emplace_back
const char nl = '\n';

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

void solve() {

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    int a[n + 1]; for(int i = 1; i <= n; ++i) cin >> a[i];
    vector<int> adj[n + 1];
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].eb(v); adj[v].eb(u);
    }
    for(int i = 1; i <= n; ++i) {
        adj[i].eb(i);
    }

    int dist[n + 1][2001];
    for(int i = 0; i <= n; ++i) for(int j = 0; j < 2001; ++j) dist[i][j] = -1;
    bool proc[n + 1][2001] = {};
    priority_queue<pair<int, pair<int, int>>> pq;

    dist[1][0] = 0;
    pq.push({-dist[1][0], {1, 0}});
    while(!pq.empty()) {
        int c = pq.top().sc.fr, h = pq.top().sc.sc;
        pq.pop();
        if(proc[c][h]) continue;
        proc[c][h] = 1;

        for(int d : adj[c]) {
            for(int dh : {-1, 0, 1}) {
                if(h + dh < 0 || h + dh > 2000) continue;
                if(proc[d][h + dh]) continue;
                if(a[d] > h + dh) continue;
                if(dist[d][h + dh] == -1 || dist[d][h + dh] > dist[c][h] + 1) {
                    dist[d][h + dh] = dist[c][h] + 1;
                    pq.push({-dist[d][h + dh], {d, h + dh}});
                }
            }
        }
    }

    cout << dist[n][0] << nl;
}