Redundant Connection

A tree with n nodes had one extra edge added to it, creating exactly one cycle. Given the n edges (as if the tree were built one edge at a time), return the edge that can be removed to restore it to a tree.

Example

Input edges: (1,2) (1,3) (2,3) Output: 2 3

Approach

Process edges in order, union-ing each pair of nodes. The very first edge whose two endpoints are already in the same component (i.e., union returns false — they were already connected before this edge) is the redundant one: adding it is what creates the cycle.

Input format

Line 1: number of edges N (also the number of nodes, 1-indexed) Next N lines: a b

Print the redundant edge, a b.