非递减彩色路径

题目描述

有一个 $N$ 个顶点、$M$ 条边的连通无向图,第 $i$ 条边双向连接顶点 $U_i$ 和顶点 $V_i$。

每个顶点上写有一个整数,顶点 $v$ 上写有整数 $A_v$。

对于从顶点 $1$ 到顶点 $N$ 的简单路径(不重复经过同一个顶点的路径),按如下方式计算得分:

• 设 $S$ 为沿路径按访问顺序排列的、路径上顶点所写整数的序列。
• 如果 $S$ 不是非递减的,则该路径的得分为 $0$。
• 否则,得分为 $S$ 中不同整数的个数。

在从顶点 $1$ 到顶点 $N$ 的所有简单路径中,求出得分最高者的得分并输出。

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

输入格式

输入按以下格式从标准输入给出。

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

输出格式

将答案作为整数输出。

样例

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

4

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

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

0

从顶点 $1$ 到顶点 $N$ 的简单路径中,不存在 $S$ 为非递减的路径。此时最大得分为 $0$。

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

5

数据范围

• 所有输入值均为整数
• $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 \lt V_i \le N$
• 若 $i \neq j$,则 $(U_i,V_i) \neq (U_j,V_j)$