A project has n tasks forming a directed acyclic graph. A directed edge u v means u must be completed before v. Define the depth level of a task as the number of edges on the longest path that ends at it, starting from some task that has no prerequisites. Tasks with no prerequisites have depth level 0. Output the depth level of every task.
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
One line with n space-separated integers: the depth level of node 0, node 1, ..., node n-1.
Constraints
- 1 <= n <= 2000
- 0 <= m <= 5000
- 0 <= u, v <= n-1; the graph is a DAG