Implement build_roads(n, roads) -> list[tuple[int, int]].
There are n cities numbered 1..n and a list of two-way roads, each a pair (a, b). Roads may repeat and may even connect a city to itself. Add as few new roads as possible so that every city can reach every other city. Return the new roads as a list of (a, b) pairs. Any valid minimum answer is accepted.
build_roads(5, [(1, 2), (3, 4), (4, 1)])
# e.g. [(1, 5)] cities {1, 2, 3, 4} are already connected, 5 is alone
build_roads(3, [])
# e.g. [(1, 2), (1, 3)]
n and len(roads) go up to 100,000, so aim for O(n + len(roads)) and avoid deep recursion (Python's default limit is about 1,000 frames).
Show hint
Think about the groups of cities that can already reach each other. How few roads does it take to join those groups?