A rooted tree has n nodes labelled 1 to n, with every edge directed from parent to child. One extra directed edge was added, so the graph now has n edges, given in edges. Return the edge to remove so that what is left is a rooted tree on all n nodes. If several edges work, return the one that appears last in the input.
- A
DSU class with find(x), union(a, b) (returns false when they were already together), setSize(x) and a components counter is already provided - The extra edge can create a node with two parents, a cycle, or both
- Plain union-find ignores direction, so deal with the two-parent case first
- Edges are distinct and never connect a node to itself