题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的连通无向图，其中第 $i$ 条边双向连接顶点 $U_i$ 和 $V_i$。

每个顶点上都写有一个整数，顶点 $v$ 上的整数为 $A_v$。

对于一条从顶点 1 到顶点 $N$ 的简单路径（即不重复经过同一顶点的路径），其得分计算方式如下：

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

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

输入格式

输入从标准输入给出，格式如下：

• $N$ $M$
• $A_1$ $A_2$ ... $A_N$
• $U_1$ $V_1$
• $U_2$ $V_2$

⋮

• $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 \to 3 \to 4 \to 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 < V_i \le N$
• 当 $i \neq j$ 时，$(U_i, V_i) \neq (U_j, V_j)$（即无重边）。