First of all, since the graph is connected, there is a path from \(1\) to \(N\). Thus, the maximum score is at least \(0\).

Therefore, what we have to consider is paths with positive scores. Consequently, we come up with the following observation on the edge connected vertex \(u\) and vertex \(v\).

• If \(A_u < A_v\), we only consider the case where this edge is used in \(u \rightarrow v\) direction.
• If \(A_u > A_v\), we can consider just as above (swapping \(u\) and \(v\)).
• If \(A_u = A_v\), this edge may be used in either direction.

Consider the following DP (Dynamic Programming):
\(dp[v] = \) { preliminary maximum score of a path from vertex \(1\) to vertex \(v\) }.

Actually, the following holds:

Let \(G\) be a graph obtained by retaining edges \(u - v\) with \(A_u = A_v\). Then, vertices belonging to the same connected component can be regarded as single vertex.

For example, if vertices \(p,q,r\), and \(s\) satisfies:

• \(A_p < A_q = A_r < A_s\);
• edge \(p - q\) exists;
• \(q\) and \(r\) belong to the same connected component on \(G\); and
• edge \(r - s\) exists,

then one can traverse \(p \rightarrow q \rightarrow \dots \rightarrow r \rightarrow s\) path without breaking the monotonicity of \(S\).

When traveling from \(q\) and \(r\), it is sufficient to take a spanning tree and use the edges in it.

After identifying vertices, all remaining edges \(u - v\) satisfy \(A_u < A_v\). In this case, the DP described above can be conducted by transitioning edges \(u - v\) with \(A_u < A_v\) in ascending order of \(A_u\). (The problem to be solved is a shortest path problem on a DAG (Directed Acyclic Graph)). On transition, do not forget identifying vertices as described above. It can be achieved by managing vertices with DSU (Disjoint Set Union).

Sample code (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;
}