Watching a social network grow its biggest circle
A new social app in Mexico City tracks friendships as they happen. Two people are in the same circle if they are connected through any chain of friendships. The growth team wants a live metric: after each new friendship is recorded, how large is the biggest circle?
Task: the first line holds n and m (1 ≤ n ≤ 200, 1 ≤ m ≤ 300). Users are numbered 1 to n and everybody starts alone. Each of the next m lines holds a b, a new friendship (it may repeat an existing friendship or have a = b, in which case nothing changes). Print m lines: after processing each event, the size of the largest circle.
Sample test
Input
6 5 1 2 3 4 2 3 5 5 5 6
Expected output
2 2 4 4 4
Your answer is also checked against 5 hidden tests.
Need a hint?
Keep each circle as a group with a representative. Merging two groups should be cheap.
Log in or create a free account to run your code, submit and earn points.
Run your code to see the output here. Ctrl + Enter also runs it.