Score : $525$ points

问题描述

存在一个含有 $N$ 个顶点和 $M$ 条边的连通无向图，其中第 $i$ 条边在顶点 $U_i$ 和顶点 $V_i$ 之间双向连接。

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

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

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

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

什么是非递减序列？长度为 $l$ 的序列 $S=(S_1,S_2,\dots,S_l)$ 被称为非递减序列，当且仅当对于所有满足 $1 \le i < l$ 的整数，都有 $S_i \le S_{i+1}$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a connected undirected graph with $N$ vertices and $M$ edges, where the $i$-th edge connects vertex $U_i$ and vertex $V_i$ bidirectionally.
Each vertex has an integer written on it, with integer $A_v$ written on vertex $v$.

For a simple path from vertex $1$ to vertex $N$ (a path that does not pass through the same vertex multiple times), the score is determined as follows:

• Let $S$ be the sequence of integers written on the vertices along the path, listed in the order they are visited.
• If $S$ is not non-decreasing, the score of that path is $0$.
• Otherwise, the score is the number of distinct integers in $S$.

Find the path from vertex $1$ to vertex $N$ with the highest score among all simple paths and print that score.

What does it mean for $S$ to be non-decreasing? A sequence $S=(S_1,S_2,\dots,S_l)$ of length $l$ is said to be non-decreasing if and only if $S_i \le S_{i+1}$ for all integers $1 \le i < l$.

Constraints

• All input values are integers.
• $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$
• The graph is connected.
• $1 \le U_i < V_i \le N$
• $(U_i,V_i) \neq (U_j,V_j)$ if $i \neq j$.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

4

The path $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ has $S=(10,30,40,50)$ for a score of $4$, which is the maximum.

Sample Input 2

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

Sample Output 2

0

There is no simple path from vertex $1$ to vertex $N$ such that $S$ is non-decreasing. In this case, the maximum score is $0$.

Sample Input 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

Sample Output 3

5

update @ 2024/3/10 01:24:12