Description

On Joitter, you can follow other users, but you cannot follow yourself and you cannot follow the same user twice. That is, following the same user multiple times only counts once.

There are $N$ new users and $M$ days.

On day $i$, user $A_i$ follows user $B_i$.

Also, after the follow action, a social event is held with the following rules:

1. Choose a user $x$.
2. Choose a user $y$ that is followed by user $x$.
3. Choose a user $z$ such that $z\not=x$, $x$ does not follow $z$, and $y$ and $z$ follow each other.
4. Make $x$ follow $z$.
5. Repeat $1,2,3,4$ until no suitable triple $(x,y,z)$ can be chosen.

You need to compute, for each $i$, the total number of follows after day $i$.

Input Format

The first line contains two integers $N,M$.

The next $M$ lines each contain two integers $A_i,B_i$.

Output Format

Output $M$ lines in total. Each line contains one number. Line $i$ represents the total number of follows after day $i$.

4 6
1 2
2 3
3 2
1 3
3 4
4 3

1
2
4
4
5
9

6 10
1 2
2 3
3 4
4 5
5 6
6 5
5 4
4 3
3 2
2 1

1
2
3
4
5
7
11
17
25
30

Hint

Subtasks

For $100\%$ of the testdata, it is guaranteed that $2\le N\le 10^5$, $1\le M\le 3\times 10^5$, $1\le A_i,B_i\le N$, $A_i\not=B_i$, and $(A_i,B_i)\not=(A_j,B_j)$.

Notes

This problem is translated from Day 2 T2 “ジョイッターで友だちをつくろう” of The 19th Japanese Olympiad in Informatics Spring Training Camp, T2 ジョイッターで友だちをつくろう.

Translated by ChatGPT 5