Contest Duration: - (local time) (300 minutes)
G - Longest Path /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

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: