Link the clusters, spread the links

A deployment has several clusters of machines. Machines inside a cluster already talk to each other; clusters don't. You'll add cross-cluster links so that every machine can reach every other one, using as few links as possible, while keeping the extra work on any one machine low.

Write connect_groups(groups: list[list[int]]) -> list[tuple[int, int]]:

• groups has K >= 1 non-empty lists of machine ids. Ids are distinct integers across all groups. Let N be the total number of machines.
• Return exactly K - 1 links (a, b). Each link joins machines from two different groups.
• If you shrink each group to a single vertex, the links must form a spanning tree: every group is reachable from every other and no link is redundant.
• The load of a machine is how many of your links touch it. Among all valid answers, yours must have the smallest possible maximum load.

Any answer meeting these rules is accepted: link order and the order inside each pair don't matter.

connect_groups([[1, 2], [3], [4, 5, 6]])
# e.g. [(1, 3), (2, 4)]    max load 1: no machine is used twice

connect_groups([[10], [20], [30], [40]])
# e.g. [(10, 20), (20, 30), (30, 40)]    max load 2: with 4 singletons some machine needs 2 links

connect_groups([[7, 8, 9]])
# []    one group, nothing to link

Constraints: up to 100,000 groups and 200,000 machines in total. Your method should be close to linear.

Things to watch:

• A star (every group linked to group 0) or a simple chain are both valid trees, but each can pile several links onto one machine when a better spread exists.
• A tree over K groups has K - 1 links and so 2(K - 1) link endpoints in total. Think about how few endpoints each group and each machine can get away with, then build a tree that meets that bound.