1023. Redundant Connection

Given an undirected graph that started as a tree with n nodes (0..n-1) and had exactly one extra edge added (forming a single cycle), return that redundant edge — the edge in the input that, when processed, first connects two already-connected nodes. If multiple qualify, return the one appearing last in the edge list. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — the redundant edge [u, v].

Examples

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: [2,0]
Explanation: The last edge closes the cycle.

Input: {"n":4,"edges":[[0,1],[1,2],[2,3],[1,3]]}
Output: [1,3]
Explanation: This edge is redundant.

Input: {"n":2,"edges":[[0,1],[0,1]]}
Output: [0,1]
Explanation: The duplicate edge.

Constraints

• 3<=n<=1000
• exactly one extra edge

Asked by