Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Redundant Connection

Medium
graphunion-find

A tree with n nodes (labeled 1…n) had exactly one extra undirected edge added. Given the resulting edge list, return the edge that can be removed to restore a tree. If several qualify, return the one appearing last in the input.

Input

  • Line 1: n n (the graph has exactly n edges)
  • Next n lines: u v

Output: the edge u v.

Example 1
Input:
3 3
1 2
1 3
2 3
Output:
2 3
Example 2
Input:
5 5
1 2
2 3
3 4
1 4
1 5
Output:
1 4

Constraints

  • 3 ≤ n ≤ 1000
  • The input is a tree plus one extra edge.
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.