Redundant Connection II

Hard

A rooted tree is a directed graph where every node has exactly one parent except the root, which has none. You start with such a tree on n nodes labelled 1 to n and add one extra directed edge.

Given the resulting edges list, where edges[i] = [u, v] is a directed edge from parent u to child v, return the edge that can be removed so the remaining graph is a rooted tree of n nodes. If several answers exist, return the one that appears last in the input.

Example 1

Input:  edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: Node 3 has two parents. Removing the later of the two edges into it leaves a valid rooted tree.

Example 2

Input:  edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]
Explanation: Every node has one parent, so the fault is a cycle. Removing the edge that closes it restores the tree.

Constraints

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= u, v <= n
• u != v