Redundant Connection (Union-Find)

A tree with nodes 1 … n had one extra edge added, so the graph now has exactly n edges and one cycle. Find an edge you can remove so the result is a tree again. If several edges qualify, print the one that appears last in the input.

Input:

• line 1: n
• next n lines: an edge a b (a < b)

Output: the edge to remove, as a b.

Constraints: 3 ≤ n ≤ 10⁵; no repeated edges; the graph is connected.

Think about it: add the edges one by one into a Union-Find. The first edge whose two ends are already connected closes the cycle — and it is the last cycle edge in the input. With path compression each step is almost O(1).