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
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