← 返回题目列表

AtCoder · awc0072_d

D. 山穿越

中文机器翻译题面 查看原题

分数: 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