// 願ったんなら叶えてしまえやって
// Think twice, code once.
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, dis[2][200005], a[200005];
struct graph {
	int tot, hd[200005];
	int nxt[800005], to[800005];

	void add(int u, int v) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		return ;
	}
} g;
struct node {
	int id, val;

	node() = default;
	node(int _id, int _val): id(_id), val(_val) {}
	bool operator<(const node &x) const {return val > x.val;}
};

void dijkstra(int s, int o) {
	priority_queue<node> q;
	memset(dis[o], 0x3f, sizeof(dis[o]));
	q.emplace(s, dis[o][s] = 0);
	while (!q.empty()) {
		int now = q.top().id, tmp = q.top().val;
		q.pop();
		if (tmp != dis[o][now]) continue;
		for (int i = g.hd[now]; i; i = g.nxt[i])
			if (dis[o][g.to[i]] > max(dis[o][now] + 1, a[g.to[i]]))
				q.emplace(g.to[i], dis[o][g.to[i]] = max(dis[o][now] + 1, a[g.to[i]]));
	}
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g.add(u, v);
		g.add(v, u);
	}
	if (n == 2) {puts("1"); return 0;}
	dijkstra(1, 0), dijkstra(n, 1);
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, 2 * max(dis[0][i], dis[1][i]));
		for (int j = g.hd[i]; j; j = g.nxt[j])
			ans = min(ans, 2 * max(dis[0][i], dis[1][g.to[j]]) + 1);
	}
	printf("%d\n", ans);
	return 0;
}