Code

#include <bits/stdc++.h>
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define space putchar (' ')
#define endl putchar ('\n')
#define pii pair <int, int>
#define rrt rt << 1 | 1
#define int long long
#define mp make_pair
#define pb push_back
#define lrt rt << 1
using namespace std;

template <typename T>
void Read (T &x)
{
	T res = 0, f = 1;
	char ch = getchar ();

	while (ch < '0' || ch > '9')
	{
		if (ch == '-') f = -1;
		ch = getchar ();
	}

	while (ch >= '0' && ch <= '9')
	{
		res = res * 10 + ch - '0';
		ch = getchar ();
	}
	x = res * f;
}

template <typename T>
void Write (T x)
{
	if (x < 0) putchar ('-'), x = -x;
	if (x > 9) Write (x / 10);
	putchar ('0' + x % 10);
}

const int N = 200010;
int n, m, a[N], fa[N];
vector <int> edges[N];
int u[N], v[N], ed;
int ans[N];

int Find_fa (int id)
{
	return (fa[id] == id) ? id : (fa[id] = Find_fa (fa[id]));
}

void Dfs (int id, int fath, int cnt)
{
	if (cnt < ans[id]) return ; ans[id] = cnt;
	if (id == ed) return ;
	
	for (auto to : edges[id]) if (to != fath) Dfs (to, id, cnt + 1);
}

signed main ()
{
	Read (n), Read (m);
	for (int i = 1; i <= n; i++) Read (a[i]), fa[i] = i;
	for (int i = 1, fau, fav; i <= m; i++)
	{
		Read (u[i]), Read (v[i]);
		if (a[u[i]] == a[v[i]])
		{
			fau = Find_fa (u[i]), fav = Find_fa (v[i]);
			if (fau != fav) fa[fav] = fau;
		}
	}
	
	for (int i = 1; i <= n; i++) fa[i] = Find_fa (i); ed = fa[n];
	for (int i = 1, fau, fav; i <= m; i++)
	{
		fau = Find_fa (u[i]), fav = Find_fa (v[i]);
		if (a[fau] == a[fav]) continue;
		if (a[fau] < a[fav]) edges[fau].pb (fav);
		else edges[fav].pb (fau);
	}
	Dfs (fa[1], -1, 1);
	Write (ans[ed]);
	return 0;
}

提交记录