缩点最长路 以及 模板的使用
// AtCoder - AtCoder Beginner Contest 335 (Sponsored by Mynavi) E -
// Non-Decreasing Colorful Path
// https://atcoder.jp/contests/abc335/tasks/abc335_e 2024-01-10 13:08:12
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
struct UnionFindSet {
vector<int> F;
vector<int> rank;
int n;
UnionFindSet(int _n = 2e5 + 10) {
n = _n;
F.resize(n + 1);
rank.resize(n + 1, 1);
for (int i = 1; i <= n; i++) {
F[i] = i;
}
}
int find(int x) { return x == F[x] ? x : F[x] = find(F[x]); }
bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (rank[fx] < rank[fy]) swap(fx, fy);
F[fy] = fx;
rank[fx] += rank[fy];
return true;
}
};
struct graph {
int n, cnt;
vector<vector<pair<int, int>>> G2;
vector<vector<int>> G;
vector<int> in, fa, dep, siz, btm, son, top, id, rk;
vector<int> f;
graph(int n = 2e5 + 10) : n(n) { init(n); }
void init(int n) {
this->n = n;
cnt = 0;
G.resize(n + 1);
G2.resize(n + 1);
in.resize(n + 1);
fa.resize(n + 1);
btm.resize(n + 1);
dep.resize(n + 1);
siz.resize(n + 1);
son.resize(n + 1);
top.resize(n + 1);
id.resize(n + 1);
rk.resize(n + 1);
f.resize(n + 1);
}
void work(int rt = 1) {
dfs1(rt, 0, 1);
dfs2(rt, rt);
}
void add(int a, int b) {
G[a].emplace_back(b);
in[b]++;
}
void add2(int a, int b, int v) {
G2[a].emplace_back(b, v);
in[b]++;
}
void dfs1(int u, int fath, int depth) {
fa[u] = fath, dep[u] = depth, siz[u] = 1;
for (auto it : G[u]) {
if (it == fath)
continue;
else {
dfs1(it, u, depth + 1);
siz[u] += siz[it];
if (siz[it] > siz[son[u]]) son[u] = it;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
id[u] = ++cnt;
rk[cnt] = u;
btm[u] = cnt;
if (!son[u])
return;
else
dfs2(son[u], t), btm[u] = cnt;
for (auto it : G[u]) {
if (it != son[u] and it != fa[u]) dfs2(it, it);
btm[u] = cnt;
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[u] < dep[v]) swap(u, v);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return u;
}
int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
int jump(int u, int k) {
if (dep[u] < k) return -1;
int d = dep[u] - k;
while (dep[top[u]] > d) u = fa[top[u]];
return rk[id[u] - dep[u] + k];
}
};
using pii = pair<int, int>;
void solve() {
cin >> n >> m;
UnionFindSet U;
vector<int> a(n + 1), f(n + 1, INT_MIN);
for (int i = 1; i <= n; i++) cin >> a[i];
graph G;
vector<pii> b;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
b.emplace_back(x, y);
if (a[x] == a[y]) U.merge(U.find(x), U.find(y));
}
for (int i = 0; i < m; i++) {
auto [x, y] = b[i];
x = U.find(x);
y = U.find(y);
if (x != y) {
G.add(x, y);
G.add(y, x);
}
}
auto dfs = [&](auto &&dfs, int u) -> int {
if (f[u] != INT_MIN) return f[u];
for (auto it : G.G[u]) {
if (a[u] > a[it]) f[u] = max(f[u], dfs(dfs, it) + 1);
}
return f[u];
};
f[U.find(1)] = 1;
int ans = dfs(dfs, U.find(n));
if (ans < 0) ans = 0;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << std::setprecision(15);
solve();
return 0;
}