A dependency graph has n items forming a directed acyclic graph, where an edge u v means u must come before v. A dependency chain is a directed path a1 -> a2 -> ... -> ak. Find the maximum number of nodes k on any such chain. A single node by itself counts as a chain of length 1.
Input format
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers , a directed edge from to (read as: must come before ).
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
Output format
A single integer: the maximum number of nodes on any directed path.
Constraints
- 1 <= n <= 2000
- 0 <= m <= 5000
- 0 <= u, v <= n-1; the graph is a DAG