D - 山岳縦走 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は山岳縦走が趣味の登山家です。ある山岳地帯には N 個の山小屋があり、山小屋には 1 から N までの番号がついています。山小屋同士は M 本の一方通行の登山道で結ばれています。j 本目の登山道は山小屋 U_j から山小屋 V_j へ一方通行で通行でき、逆方向には通行できません。

各山小屋 i には標高 P_i が設定されています。すべての山小屋の標高は互いに異なります。

高橋君は山小屋 1 から出発し、登山道を辿りながら縦走を行います。山小屋の列 v_1, v_2, \ldots, v_k（k \geq 1）が以下の条件をすべて満たすとき、これを「よい縦走」と呼びます。

  • v_1 = 1 である。すなわち、山小屋 1 から出発する。
  • すべての i（1 \leq i \leq k-1）について、山小屋 v_i から山小屋 v_{i+1} への一方通行の登山道が存在する。
  • すべての i（1 \leq i \leq k-1）について P_{v_i} < P_{v_{i+1}} が成り立つ。すなわち、連続して訪れる山小屋の標高が 狭義単調増加 になっている。

「よい縦走」は任意の山小屋で終了してよく、終点に関する制約はありません。また、山小屋 1 のみにいて登山道を 1 本も辿らない場合（k = 1）も「よい縦走」に該当します。したがって、答えは必ず 1 以上です。

高橋君はできるだけ多くの山小屋を巡りたいと考えています。「よい縦走」において訪れる山小屋の数 k の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • P_i はすべて異なる。
  • 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 同じ組 (U_j, V_j) が複数回与えられることはない。
  • 入力はすべて整数である。

入力

N M
P_1 P_2 \cdots P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、山小屋の数を表す整数 N と、登山道の数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各山小屋の標高を表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。P_i は山小屋 i の標高を表す。
  • 続く M 行にわたり、登山道の情報が与えられる。そのうち j 行目（入力全体の 2 + j 行目）には、j 本目の登山道の始点 U_j と終点 V_j がスペース区切りで与えられる。これは山小屋 U_j から山小屋 V_j への一方通行の登山道が存在することを意味する。

出力

「よい縦走」において訪れることができる山小屋の数の最大値を 1 行で出力せよ。

入力例 1

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

出力例 1

4

入力例 2

4 4
100 50 30 200
1 2
1 3
2 4
3 4

出力例 2

1

入力例 3

8 9
15 30 10 45 25 50 35 60
1 2
1 5
2 4
5 7
7 4
4 6
6 8
1 3
3 5

出力例 3

6

入力例 4

15 20
5 50 10 45 15 40 20 35 25 30 55 60 65 70 75
1 3
3 5
5 7
7 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 4
4 6
6 8
1 5
3 7
5 9
9 11
7 10
2 6

出力例 4

11

入力例 5

1 0
1000000000

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is a mountaineer whose hobby is mountain traversing. In a certain mountainous region, there are N mountain huts, numbered from 1 to N. The mountain huts are connected by M one-way mountain trails. The j-th trail allows one-way passage from mountain hut U_j to mountain hut V_j, and cannot be traversed in the reverse direction.

Each mountain hut i has an elevation P_i. All mountain huts have distinct elevations.

Takahashi starts from mountain hut 1 and performs a traverse by following mountain trails. A sequence of mountain huts v_1, v_2, \ldots, v_k (k \geq 1) is called a "good traverse" if it satisfies all of the following conditions:

  • v_1 = 1. That is, the traverse starts from mountain hut 1.
  • For all i (1 \leq i \leq k-1), there exists a one-way mountain trail from mountain hut v_i to mountain hut v_{i+1}.
  • For all i (1 \leq i \leq k-1), P_{v_i} < P_{v_{i+1}} holds. That is, the elevations of consecutively visited mountain huts are strictly monotonically increasing.

A "good traverse" may end at any mountain hut; there is no constraint on the endpoint. Additionally, staying only at mountain hut 1 without following any trail (k = 1) also counts as a "good traverse". Therefore, the answer is always at least 1.

Takahashi wants to visit as many mountain huts as possible. Find the maximum value of k, the number of mountain huts visited in a "good traverse".

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • All P_i are distinct.
  • 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • The same pair (U_j, V_j) is not given more than once.
  • All input values are integers.

Input

N M
P_1 P_2 \cdots P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains an integer N representing the number of mountain huts and an integer M representing the number of mountain trails, separated by a space.
  • The second line contains integers P_1, P_2, \ldots, P_N representing the elevations of each mountain hut, separated by spaces. P_i represents the elevation of mountain hut i.
  • The following M lines contain the information about the mountain trails. The j-th of these lines (the (2 + j)-th line of the entire input) contains the starting point U_j and the ending point V_j of the j-th trail, separated by a space. This means there exists a one-way mountain trail from mountain hut U_j to mountain hut V_j.

Output

Output in one line the maximum number of mountain huts that can be visited in a "good traverse".

Sample Input 1

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

Sample Output 1

4

Sample Input 2

4 4
100 50 30 200
1 2
1 3
2 4
3 4

Sample Output 2

1

Sample Input 3

8 9
15 30 10 45 25 50 35 60
1 2
1 5
2 4
5 7
7 4
4 6
6 8
1 3
3 5

Sample Output 3

6

Sample Input 4

15 20
5 50 10 45 15 40 20 35 25 30 55 60 65 70 75
1 3
3 5
5 7
7 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 4
4 6
6 8
1 5
3 7
5 9
9 11
7 10
2 6

Sample Output 4

11

Sample Input 5

1 0
1000000000

Sample Output 5

1