Longest Non-decreasing Subsequence in a DAG

You are given a directed acyclic graph (DAG) with \( n \) nodes and \( m \) edges. The nodes are numbered from \( 1 \) to \( n \) and each node \( i \) has an associated weight \( w_i \). For any path in the DAG, we can extract the sequence of node weights following the order in which the nodes appear in the path. Your task is to determine the maximum length of the longest non-decreasing subsequence among all these weight sequences.

A subsequence \( S' = [a_{i_1}, a_{i_2}, \dots, a_{i_k}] \) of a sequence \( S \) is called non-decreasing if \( a_{i_1} \le a_{i_2} \le \cdots \le a_{i_k} \). For example, if \( S = [11,12,13,9,8,17,19] \), one longest non-decreasing subsequence is \( [11,12,13,17,19] \) which has length \( 5 \).

Note: The subsequence is not necessarily contiguous in the original path. However, the chosen elements must appear in the same order as in the path. Moreover, the subsequence is derived from some valid path in the DAG.

Input Format:

• The first line contains two integers \( n \) and \( m \).
• The second line contains \( n \) integers, the \( i\)-th of which is \( w_i \), representing the weight of node \( i \).
• Each of the next \( m \) lines contains two integers \( u \) and \( v \), indicating a directed edge from node \( u \) to node \( v \). It is guaranteed that the graph is acyclic.

Output Format:

• Output a single integer denoting the maximum length of the longest non-decreasing subsequence among all paths in the graph.

Constraints: (Not explicitly given, but you may assume \( n \) is small enough to allow an \( O(n^2) \) algorithm.)

inputFormat

The input begins with a line containing two integers \( n \) and \( m \). The next line contains \( n \) integers \( w_1, w_2, \dots, w_n \) representing the weights of nodes \( 1 \) to \( n \). This is followed by \( m \) lines, each containing two integers \( u \) and \( v \) representing a directed edge from node \( u \) to node \( v \).

outputFormat

Output a single integer — the maximum length of the longest non-decreasing subsequence among all paths in the DAG.

sample

3 2
2 1 2
1 2
2 3

2