Longest Cycle of Successors

A directed graph is given as a list nxt where every node i has at most one outgoing edge: nxt[i] is the node it points to, or -1 if it has none. Return the length (number of edges) of the longest directed cycle in the graph, or -1 if there is no cycle.

Examples

Input:  nxt = [3,3,4,2,3]
Output: 3
Explanation: 2 -> 4 -> 3 -> 2 is a cycle of length 3. Nodes 0 and 1 lead into it but are not on it.

Input:  nxt = [2,-1,3,1]
Output: -1
Explanation: 0 -> 2 -> 3 -> 1 ends at a node with no outgoing edge.

Constraints

• 1 <= len(nxt) <= 10**5, nxt[i] == -1 or 0 <= nxt[i] < len(nxt)
• nxt[i] == i is allowed (a cycle of length 1).
• Target O(n) time - every node must be walked at most once overall.

Goals

• Detect directed cycles using per-walk timestamps
• Avoid re-walking nodes that an earlier walk already covered