#include<cstdio>
#include<queue>
using namespace std;
const int N=200086,M=400086,INF=2e9;
int n,m,tot=1,a[N],d[2][N],eu[M],ev[M],h[N];
struct edge{int v,nxt;}e[M<<1];
struct node{
	int no,dis;
	node(int n,int d){no=n;dis=d;}
	bool operator <(const node b)const{return b.dis>dis;}
};
priority_queue<node>q;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool add(int u,int v){e[++tot].v=v;e[tot].nxt=h[u];h[u]=tot;return true;}
bool dij(int s,int flr){
	for(int i=1;i<=n;i++)d[flr][i]=INF;
	while(!q.empty())q.pop();q.push(node(s,d[flr][s]=0));
	while(!q.empty()){
		node np=q.top();q.pop();if(np.dis!=d[flr][np.no])continue;
		for(int i=h[np.no];i;i=e[i].nxt){
			int nd=Max(d[flr][np.no]+1,a[e[i].v]);
			if(nd<d[flr][e[i].v])q.push(node(e[i].v,d[flr][e[i].v]=nd));
		}
	}
	return true;
}
int main(){
	n=read();m=read();for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++){
		eu[i]=read();ev[i]=read();
		add(eu[i],ev[i]);add(ev[i],eu[i]);
	}
	dij(1,0);dij(n,1);int ans=INF;
	for(int i=2;i<n;i++)ans=Min(ans,Max(d[0][i],d[1][i])*2);
	for(int i=1;i<=m;i++){
		ans=Min(ans,Max(d[0][eu[i]],d[1][ev[i]])*2+1);
		ans=Min(ans,Max(d[0][ev[i]],d[1][eu[i]])*2+1);
	}
	printf("%d",ans);
}