E - Non-Decreasing Colorful Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

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 < l について S_i \le S_{i+1} を満たすことを言います。

制約

  • 入力は全て整数
  • 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)

入力

入力は以下の形式で標準入力から与えられる。

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

Score : 525 points

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