#177MediumGraphs· Union-Find

The Redundant Cable

A campus network connects `n` buildings, numbered `1` to `n`, with exactly `n` cables. Every building can reach every other building, but one cable is redundant: removing it would still leave the network connected, and the cables would then form a tree. Cables are listed in the order they were installed, each as a pair `[u, v]` of buildings. If several cables could be removed to leave a tree, the technician wants the one that appears **latest** in the list. Return that cable as it appears in the input.

Input format

`cables`: an array of `n` pairs `[u, v]` describing an undirected connected network.

Output format

The pair `[u, v]` of the cable to remove, exactly as written in the input.

Examples

Input: cables = [[1, 2], [1, 3], [2, 3]]

Output: [2, 3]

The three cables form a triangle. Any of them could be removed, and the latest is [2, 3].

Input: cables = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

Output: [1, 4]

The cycle is 1-2-3-4-1. The latest of its cables in the list is [1, 4]; cable [1, 5] is not on the cycle.

Input: cables = [[2, 1], [3, 1], [3, 2]]

Output: [3, 2]

Endpoints can be written in either order; the answer keeps the input order of the chosen cable.

Constraints

3 <= n <= 10^4 (the number of buildings, which equals cables.length)
1 <= u, v <= n and u != v
No cable is repeated, and the network is connected.

Study first

#graph
#union-find
#disjoint-set
#cycle-detection