Redundant Connection

Medium

A tree on nodes 1..n had one extra edge added, creating exactly one cycle. Given the edges in input order, return the edge that can be removed so the result is a tree. If several qualify, return the one that appears last in the input.

Example 1

Input:  edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2

Input:  edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Constraints

• 3 <= n <= 1000
• The graph is a tree plus exactly one extra edge.