まず、グラフが連結であることから、 \(1\) から \(N\) へのパスが存在します。このことから、最大スコアが \(0\) 以上であることが分かります。

そうすると、考慮するべきはスコアが正であるようなパスです。ここから、頂点 \(u\) と頂点 \(v\) を結ぶ辺について以下のような考察が導けます。

• \(A_u < A_v\) なら、この辺を \(u \rightarrow v\) の向きに通る場合のみ考えればよい。
• \(A_u > A_v\) なら、 ( \(u,v\) を入れ替えて ) 上の場合と同様に処理すればよい。
• \(A_u = A_v\) なら、この辺はどちら向きにも通りうる。

以下のような DP を考えます。
\(dp[v] = \) { 頂点 \(1\) から頂点 \(v\) へのパスの暫定最高スコア }

実は、以下のことが言えます。

\(A_u = A_v\) なる辺 \(u - v\) のみを残したグラフを \(G\) とする。このとき、 \(G\) 上で同じ連結成分に属する頂点たちはひとつの頂点として同一視してよい。

例えば、

• \(A_p < A_q = A_r < A_s\)
• 辺 \(p - q\) が存在する。
• 頂点 \(q,r\) が \(G\) 上で同じ連結成分に属する。
• 辺 \(r - s\) が存在する。

なる頂点 \(p,q,r,s\) について、 \(p \rightarrow q \rightarrow \dots \rightarrow r \rightarrow s\) パスを \(S\) の単調増加性を崩さないように通ることができます。

\(q\) から \(r\) への移動には \(G\) 上の \(q,r\) が属する連結成分の全域木をひとつ取り、そこに含まれる辺を用いればよいです。

さて、頂点同一視の後残るものは \(A_u < A_v\) なる辺 \(u - v\) のみです。
このとき、先ほど述べた \(dp\) は \(A_u < A_v\) なる辺 \(u - v\) を \(A_u\) の小さい順に遷移させれば求めることができます。 ( 解くべき問題が、 DAG 上の最長経路問題となっています。 )
遷移を行う際、先ほど行った頂点同一視を忘れないよう注意してください。頂点同一視は、 UnionFind などを用いて管理することができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  UnionFind uf(n);
  vector<vector<pair<int,int>>> vp(200005);
  for(int i=0;i<m;i++){
    int u,v;
    cin >> u >> v;
    u--;v--;
    if(a[u]>a[v]){swap(u,v);}
    if(a[u]==a[v]){uf.unionSet(u,v);}
    else{vp[a[u]].push_back({u,v});}
  }

  vector<int> dp(200005,-1e9);
  dp[uf.root(0)]=1;
  for(auto &nx : vp){
    for(auto [u,v] : nx){
      u=uf.root(u);
      v=uf.root(v);
      if(dp[u]>0){
        dp[v]=max(dp[v],dp[u]+1);
      }
    }
  }
  cout << max(0,dp[uf.root(n-1)]) << "\n";
  return 0;
}