Networks After Each Cable

There are n computers, numbered 0 to n - 1, and none of them are connected. Technicians lay cables one at a time, and the cable (a, b) connects computers a and b. Computers connected directly or through other computers form one network, and a computer on its own is a network of one.

Write groups_after_each(n, links) that returns a list with one tuple per cable in links: (networks, largest), the number of separate networks and the number of computers in the biggest one, right after that cable is laid.

Examples

groups_after_each(5, [(0, 1), (2, 3), (1, 0), (1, 3)])
# returns [(4, 2), (3, 2), (3, 2), (2, 4)]

groups_after_each(3, [(0, 0)])
# returns [(3, 1)]

In the first example the third cable changes nothing, because 1 and 0 are already in the same network. The last cable joins the networks {0, 1} and {2, 3}.

Constraints

• 1 <= n <= 100,000 and 0 <= len(links) <= 100,000
• 0 <= a, b < n; a cable may join a computer to itself or repeat an earlier connection
• Searching a whole network again after every cable is far too slow at this size.

Note

A network can grow to 100,000 computers, more levels than Python lets a function call itself. If you walk up to a network's leader, do it with a loop rather than with recursion.