Terratechnica and Competition Level

0

0 votes
Medium
Problem

In this edition of Terratechnica we put a hell lot of events and so we are really excited to see the competition.
 But any competition is interesting when it is like real madrid versus Barcelona or Golden State versus Boston or even ECE versus EEE Basketball match (Competitive).
 But it is very boring when the competition goes one sided as India versus Bangladesh Cricket match or CSE versus (EEE or ECE) Basketball or Table-Tennis match.
 So keeping these things in mind we decided to see how competitive an event was and so the criteria was the minimum difference in the points or scores of participants will tell us the competitive level of the event. But the problem is we need to keep track of competitive level at each stage of the event just to have a data for future purpose so that we can make the event more competitive in upcoming editions.Keeping all above things in mind we decided to let the participants merge to form a team to make the event more competitive.
 But its not an easy task to keep track at each time for the organizers so they asked you to print the competitive level at each point of time.
Remember lower the competitive level value means it was more interesting event.

INPUT

First line of input contains N Q
where N denotes number of participants in the event and Q denotes the number of steps happened.
next Q lines contains A B denoting player A and B are combined as a team and now have points(A)+points(B) points.

Note: Intially everyone has 1 point

OUTPUT

For east step print the current competitive level of the game. if only one group remains print 0.

Constraints:

1 <= N <= 10^5

1 <= Q <= 10^5

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

participants 1 and 2 merged making their points 2 but 3 and 4 have 1 points so competition level is (1-1)=0 participants 3 and 4 merged making their points 2 so now competition level (2-2)=0 participants 2 and 3 merged making everyone's count to 4 but there is no other team left so we printed 0

Editor Image

?