Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1107.

Problem Description

Xiao Yang has a directed acyclic graph (DAG) with $n$ nodes and $m$ edges, where the nodes are numbered from $1$ to $n$.

For the node with index $i$, its weight is $A_i$. For any path in the graph, following the order of nodes visited along the path gives a sequence of node weights. Xiao Yang wants to know, among all possible sequences in the graph, the maximum possible length of the longest non-decreasing subsequence.

Note: Given a sequence $S$, its longest non-decreasing subsequence $S'$ is a subsequence of $S$ such that $S'$ is non-decreasing, and its length is as large as possible among all non-decreasing subsequences. For example, given $S = [11,12,13,9,8,17,19]$, its longest non-decreasing subsequence is $S' = [11,12,13,17,19]$, with length $5$.

Input Format

The first line contains two positive integers $n, m$, representing the number of nodes and the number of edges.

The second line contains $n$ positive integers $A_1, A_2, \dots A_n$, representing the node weights of nodes $1$ to $n$.

Then $m$ lines follow, each containing two positive integers $u_i, v_i$, indicating that the $i$-th edge connects node $u_i$ to node $v_i$, directed from $u_i$ to $v_i$.

Output Format

Output one line containing one integer, representing the answer.

5 4
2 10 6 3 1
5 2
2 3
3 1
1 4

3

6 11
1 1 2 1 1 2
3 2
3 1
5 3
4 2
2 6
3 6
1 6
4 6
1 2
5 1
5 4

4

6 11
5 9 10 5 1 6
5 4
5 2
4 2
3 1
5 3
6 1
4 1
4 3
5 1
2 3
2 1

4

Hint

Constraints

For all testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$, and $1 \leq A_i \leq 10$.

Translated by ChatGPT 5