Longest Path in a DAG

You are given a directed acyclic graph (DAG) with n vertices and m directed edges. The vertices are numbered from 1 to n. A path in this graph is a sequence of vertices such that there is a directed edge from one vertex to the next. The length of the path is defined as the number of edges in it.

Your task is to compute the length of the longest path in the graph. Note that the graph does not contain cycles and there might be vertices that are unreachable from any other vertex. In such cases, a vertex with no incoming edges is treated as having a starting distance (or path length) of 0.

Input/Output Specification

inputFormat

The input is read from stdin and has the following format:

n m
u1 v1
u2 v2
...
um vm

Here, the first line contains two integers, n (the number of vertices) and m (the number of edges). Each of the next m lines contains two space-separated integers u and v which represent a directed edge from vertex u to vertex v.

outputFormat

The output should be written to stdout and consists of a single integer: the length of the longest path in the DAG.

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

4