分数: 400 分
问题陈述
高桥是一名登山爱好者,爱好是登山。在某山区,有 N 山间小屋,编号自 1 to N。山间小屋由 M 单向山路。的 j第一条小路允许从山间小屋单向通行 U_j 去山间小屋 V_j,并且不能反向移动。
各山间小屋 i 具有海拔 P_i。所有的山间小屋都有不同的海拔。
高桥从山间小屋出发 1 并沿着山路进行穿越。一系列山间小屋 v_1, v_2, \ldots, v_k (k \geq 1) 如果满足以下所有条件,则称为“良好遍历”:
- v_1 = 1。即从山间小屋开始遍历 1.
- 对于所有人 i (1 \leq i \leq k-1),从山间小屋出发有一条单程山路 v_i 去山间小屋 v_{i+1}.
- 对于所有人 i (1 \leq i \leq k-1), P_{v_i} < P_{v_{i+1}} 成立。即连续访问的山间小屋的海拔为 严格单调递增.
一次“好的穿越”可能会在任何山间小屋结束;对端点没有限制。另外,只住山间小屋 1 没有跟踪任何踪迹(k = 1)也算作“良好遍历”。因此,答案至少总是 1.
高桥想要参观尽可能多的山间小屋。找到最大值 k,“良好遍历”中访问的山间小屋的数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 全部 P_i 是不同的。
- 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
- U_j \neq V_j (1 \leq j \leq M)
- 同一对 (U_j, V_j) 未给出多次。
- 所有输入值均为整数。
输入
N M P_1 P_2 \cdots P_N U_1 V_1 U_2 V_2 \vdots U_M V_M
- 第一行包含一个整数 N 代表山间小屋的数量和一个整数 M 代表山间步道的数量,以空格分隔。
- 第二行包含整数 P_1, P_2, \ldots, P_N 代表每个山间小屋的标高,以空格分隔。 P_i 代表山间小屋海拔 i.
- 以下 M 行包含有关山路的信息。的 j- 这些行( (2 + j)-整个输入的第行)包含起点 U_j 和终点 V_j 的 j第一条路径,以空格分隔。这意味着存在一条从山间小屋出发的单向山路 U_j 去山间小屋 V_j.
输出
一行输出“好遍历”中可以访问的山间小屋的最大数量。
示例输入 1
5 4 10 20 30 40 5 1 2 2 3 3 4 1 3
示例输出 1
4
示例输入 2
4 4 100 50 30 200 1 2 1 3 2 4 3 4
示例输出 2
1
示例输入 3
8 9 15 30 10 45 25 50 35 60 1 2 1 5 2 4 5 7 7 4 4 6 6 8 1 3 3 5
示例输出 3
6
示例输入 4
15 20 5 50 10 45 15 40 20 35 25 30 55 60 65 70 75 1 3 3 5 5 7 7 9 9 10 10 11 11 12 12 13 13 14 14 15 1 2 2 4 4 6 6 8 1 5 3 7 5 9 9 11 7 10 2 6
示例输出 4
11
示例输入 5
1 0 1000000000
示例输出 5
1