Social Network
Contest: Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 1600
Tags: dsu, graphs, greedy, implementation, trees

William arrived at a conference dedicated to cryptocurrencies. Networking, meeting new people, and using friends' connections are essential to stay up to date with the latest news from the world of cryptocurrencies.

The conference has $$$n$$$ participants, who are initially unfamiliar with each other. William can introduce any two people, $$$a$$$ and $$$b$$$, who were not familiar before, to each other.

William has $$$d$$$ conditions, $$$i$$$'th of which requires person $$$x_i$$$ to have a connection to person $$$y_i$$$. Formally, two people $$$x$$$ and $$$y$$$ have a connection if there is such a chain $$$p_1=x, p_2, p_3, \dots, p_k=y$$$ for which for all $$$i$$$ from $$$1$$$ to $$$k - 1$$$ it's true that two people with numbers $$$p_i$$$ and $$$p_{i + 1}$$$ know each other.

For every $$$i$$$ ($$$1 \le i \le d$$$) William wants you to calculate the maximal number of acquaintances one person can have, assuming that William satisfied all conditions from $$$1$$$ and up to and including $$$i$$$ and performed exactly $$$i$$$ introductions. The conditions are being checked after William performed $$$i$$$ introductions. The answer for each $$$i$$$ must be calculated independently. It means that when you compute an answer for $$$i$$$, you should assume that no two people have been introduced to each other yet.

Input format:
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 10^3, 1 \le d \le n - 1$$$), the number of people, and number of conditions, respectively.

Each of the next $$$d$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \neq y_i$$$), the numbers of people which must have a connection according to condition $$$i$$$.

Output format:
Output $$$d$$$ integers. $$$i$$$th number must equal the number of acquaintances the person with the maximal possible acquaintances will have, if William performed $$$i$$$ introductions and satisfied the first $$$i$$$ conditions.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The explanation for the first test case:

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that William introduced two connected people. The person marked with red has the most acquaintances. These are not the only correct ways to introduce people.

Example input:
7 6
1 2
3 4
2 4
7 6
6 5
1 7

Example output:
1
1
3
3
3
6

Example input:
10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4

Example output:
1
2
3
4
5
5
6
8

Editorial:
Note that the conditions form a collection of disjoint sets. Consider two situations:
1. The next condition connects two previously unconnected sets: then we will simply unite.
2. The next condition connects two previously connected sets: this case allows us to "postpone" an edge to use it as we like.
The second observation is that inside a set, the most advantageous construction for us has the shape of a star (a star is a graph, wherefrom one vertex there is an edge to all the others in this set). It remains not to forget about the deferred ribs. We can use them to connect some sets. The most profitable solution would be to connect sets with maximum sizes. The constraints of the problem make it possible to do this by a simple traversal over the sets in the order of sorting by the number of vertices in them.
Note that it was possible to solve the problem for more complex constraints using a tree of segments or two set<>, but this was not required in this problem.