Once we know the strategy for the reversed case (see the official editorial if you don’t know it yet), we can just simulate the whole process. More specifically, we find the cycle in the case where the current vertex is a leaf, and then redirect all the outward edges from the vertices in the cycle to the current vertex.

Now let’s prove the time complexity. For the first part, the path from the current vertex to the cycle will turn into a cycle after the operation, so we only need to calculate the complexity of the total length of cycles involved.

Define the value \(V(S)\) of a state \(S\) as the sum of squares of inward degree of all vertices. For an operation that turn state \(S\) into \(S'\) where a cycle of length \(L\) is involved, the degree of all vertices on the cycle is now \(1\) less, which results in a decrease of at most \(N\) in the value. Meanwhile, the degree of the current vertex increases by \(L\), which results in an increase of at least \(L^2\) in the value.

Since the value of a state is at most \(N^2\), we know that the sum of \(L^2\) in all operations is at most \(O(N^2)\), which gives us a clear upper bound \(O(N \sqrt N)\) on the time complexity.

(Since this process is similar to union-find set, further tighter bounds may be achievable.)