For some strange reason, my code to compress a directed graph into a DAG and run some process on it gets TLE on this problem 894E - Ralph and Mushrooms.

This is strange, because N = M = 1e6 at maximum. In addition, I used to have a log factor which I removed (using math instead), but it still gets TLE on test case 14.

My solution to the problem (41978175) is pretty much same idea as editorial, up until the last point. Instead of running toposort/dp on the DAG, I just traverse down and take the maximum path, but complexity of the function should still be O(N+M).

I am baffled by how this would TLE, can anybody give me some advice on constant optimizations or how the complexity could possibly be worse than imagined?