Longest Path in a Directed Acyclic Graph

You are given a directed acyclic graph (DAG) with N locations and M directed edges. Your task is to compute the length of the longest path in the graph in terms of the number of edges, such that no location is visited more than once.

Recall that a path v₁ → v₂ → ... → v_k has a length of \(k-1\) edges. If the graph contains no edges, then the answer is 0. The graph is guaranteed to contain no cycles.

inputFormat

Input is read from standard input (stdin). The first line contains two integers (N) and (M), where (N) is the number of locations and (M) is the number of directed edges. The following (M) lines each contain two integers (u) and (v) indicating a directed edge from location (u) to location (v). Locations are numbered from 1 to (N).

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest path (i.e. the maximum number of edges) in the graph.## sample

6 7
1 2
2 3
3 4
4 5
5 6
3 6
1 5

5