Longest Path DP

[pradeexsu]

Problem Statement

There is a directed graph G
with N vertices and M edges. The vertices are numbered 1,2,…,N, and for each i (1≤i≤M), the i-th 
directed edge goes from Vertex xi to yi. 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≤N≤105

1≤M≤105
1≤xi,yi≤N
All pairs (xi,yi) are distinct.
G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:

N M
x1 y1
x2 y2
:
xM yM

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

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2

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: note : your code should pass all the test case of G - Longest Path read README.md file carefully

[KRHero03]

Hi, Can I get this assigned?