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

const int N = 2e5 + 10;

using pii = pair<int, int>;
vector<int> g[N];

int n, m;
int a[N], dis[2][N];

void dijkstra(int st, int *dis) {
    memset(dis + 1, 0x3f, sizeof(int) * n);
    dis[st] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push({0, st});
    while(q.size()) {
        auto [d, u] = q.top();
        q.pop();

        if(d > dis[u]) continue;

        for(auto v : g[u]) {
            if(max(d + 1, a[v]) < dis[v]) {
                dis[v] = max(d + 1, a[v]);
                q.push({dis[v], v});
            }
        }
    }
}

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

    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    for(int i = 1, u, v; i <= m; i ++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dijkstra(1, dis[0]);
    dijkstra(n, dis[1]);
    int ans = 1e9;
    for(int i = 1; i <= n; i ++)
        if(abs(dis[0][i] - dis[1][i]) <= 1)
            ans = min(ans, dis[0][i] + dis[1][i] + abs(dis[0][i] - dis[1][i]));
    cout << ans;
}