An org chart with n people numbered 1 .. n was a rooted tree: exactly one person (the root) reports to nobody, everyone else reports to exactly one person, and every person is reachable from the root by following reporting lines downward. Then one extra directed edge was added between two existing people (never from a person to themselves), giving the list edges of n pairs [u, v] meaning "v reports to u".
Return the edge that must be removed so that what remains is again a rooted tree with n people. If several edges would work, return the one that appears last in edges.
Examples
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: person 3 reports to both 1 and 2; dropping either works, [2, 3] comes last.
Input: edges = [[1, 2], [2, 3], [3, 1], [3, 4]]
Output: [3, 1]
Explanation: nobody has two managers, but 1 -> 2 -> 3 -> 1 is a loop; [3, 1] is its last edge.
Input: edges = [[2, 1], [3, 1], [4, 2], [1, 4]]
Output: [2, 1]
Explanation: person 1 has two managers; removing [3, 1] would leave the loop 1 -> 4 -> 2 -> 1, so [2, 1] must go.
Constraints
3 <= n = len(edges) <= 10**4,1 <= u, v <= n,u != v- Target: O(n * alpha(n)) time.
Goals
- Distinguish the two ways an extra directed edge can break a rooted tree
- Use union-find on a directed edge list to detect the cycle case
- Combine both cases with the tie-breaking rule 'last in the list'