Joitter Friend-Making Process

In the social network Joitter, there are ( N ) new users and the system runs for ( M ) days. Each day, a manual follow event is issued: on day ( i ), user ( A_i ) follows user ( B_i ). A user cannot follow themselves, and multiple follow attempts from one user to another count only once.

After each manual follow event, a friend‐making process is triggered repeatedly as follows until no more valid triples can be found:

1. Choose a user \( x \).
2. Choose a user \( y \) such that \( x \) follows \( y \).
3. Choose a user \( z \) satisfying: \( z \neq x \), \( x \) is not following \( z \), and \( y \) and \( z \) are mutual followers (i.e. both \( y \) follows \( z \) and \( z \) follows \( y \) hold).
4. Add the follow relationship from \( x \) to \( z \).
5. Repeat from step 1.

The effect of the process is that whenever two users are in a mutual following relationship (i.e. they are "friends"), any user who follows one of them will eventually follow the other.
For each day ( i ), you are required to output the total number of follow relationships (after the closure by the friend‐making process is complete) among all users. Remember, self-follows are not allowed.

inputFormat

The first line contains two integers ( N ) and ( M ), representing the number of users and the number of days respectively. Each of the following ( M ) lines contains two integers ( A_i ) and ( B_i ), denoting that on day ( i ), user ( A_i ) follows user ( B_i ).

outputFormat

Output ( M ) lines. The ( i )th line should contain a single integer representing the total number of follow relationships (excluding self-follows) after day ( i ), after performing the friend‐making process.

sample

3 3
1 2
2 1
2 3

1
2
3