← 返回题目列表

AtCoder · abc335_e

H. 非递减彩色路径

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

分数: 525 点

问题陈述

有一个连通无向图 N 顶点和 M 边缘,其中 i第一条边连接顶点 U_i 和顶点 V_i 双向。
每个顶点上面都写有一个整数,整数 A_v 写在顶点上 v.

对于从顶点开始的简单路径 1 到顶点 N (不多次经过同一顶点的路径),分数确定如下:

  • 让 S 是沿路径写在顶点上的整数序列,按访问顺序列出。
  • If S 不是非递减的,该路径的分数是 0.
  • 否则,分数是不同整数的数量 S.

查找从顶点开始的路径 1 到顶点 N 在所有简单路径中得分最高并打印该得分。

这意味着什么 S 非递减? 一个序列 S=(S_1,S_2,\dots,S_l) 长度 l 被认为是非递减的当且仅当 S_i \le S_{i+1} 对于所有整数 1 \le i < l.

约束

  • 所有输入值均为整数。
  • 2 \le N \le 2 \times 10^5
  • N-1 \le M \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5
  • 该图已连接。
  • 1 \le U_i < V_i \le N
  • (U_i,V_i) \neq (U_j,V_j) if i \neq j.

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

输出

将答案打印为整数。


示例输入 1

5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5

示例输出 1

4

路径 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 有 S=(10,30,40,50) 得分为 4,这是最大值。


示例输入 2

4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4

示例输出 2

0

没有从顶点开始的简单路径 1 到顶点 N 这样 S 不减少。在这种情况下,最高分数是 0.


示例输入 3

10 12
1 2 3 3 4 4 4 6 5 7
1 3
2 9
3 4
5 6
1 2
8 9
4 5
8 10
7 10
4 6
2 8
6 7

示例输出 3

5