G - Longest Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 頂点 M 辺の有向グラフ G があります。 頂点には 1, 2, \ldots, N と番号が振られています。 各 i (1 \leq i \leq M) について、i 番目の有向辺は頂点 x_i から y_i へ張られています。 G は有向閉路を含みません。

G の有向パスのうち、最長のものの長さを求めてください。 ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。

制約

  • 入力はすべて整数である。
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq x_i, y_i \leq N
  • ペア (x_i, y_i) はすべて相異なる。
  • G は有向閉路を含まない。

入力

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

N M
x_1 y_1
x_2 y_2
:
x_M y_M

出力

G の有向パスのうち、最長のものの長さを出力せよ。

入力例 1

4 5
1 2
1 3
3 2
2 4
3 4

出力例 1

3

次図の赤い有向パスが最長です。

入力例 2

6 3
2 3
4 5
5 6

出力例 2

2

次図の赤い有向パスが最長です。

入力例 3

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

出力例 3

3

例えば、次図の赤い有向パスが最長です。

Score : 100 points

Problem Statement

There is a directed graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and for each i (1 \leq i \leq M), the i-th directed edge goes from Vertex x_i to y_i. G does not contain directed cycles.

Find the length of the longest directed path in G. Here, the length of a directed path is the number of edges in it.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq x_i, y_i \leq N
  • All pairs (x_i, y_i) are distinct.
  • G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the length of the longest directed path in G.

Sample Input 1

4 5
1 2
1 3
3 2
2 4
3 4

Sample Output 1

3

The red directed path in the following figure is the longest:

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2

The red directed path in the following figure is the longest:

Sample Input 3

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

Sample Output 3

3

The red directed path in the following figure is one of the longest: