399. The Longest Chain of Arrows
The edges are directed. Print the number of edges on the longest path that
follows arrows, or IMPOSSIBLE if the graph has a directed cycle.
The IMPOSSIBLE case is not an aside; it is the reason the rest works. On a
graph with a cycle there is no longest path at all, since you can go round again
for one more edge. Once there is no cycle, every path ends.
Longest paths are hard in general and easy here, and topological order is what
makes the difference. Take the vertices in the order from problem 380. By the
time you reach vertex v, every vertex with an arrow into v has already been
settled, so the best route reaching v is one more than the best among those
predecessors. One pass in that order fills in every answer.
Trying every path instead is exponential. The order is doing real work.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
directed edges. Each of the next m lines contains two integers u and v,
a directed edge from u to v and NOT from v to u. Vertices are numbered
1 to n.
Output
Print one integer, the number of edges on the longest directed path, or the word
IMPOSSIBLE.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.