P7212 [JOISC 2020] Let’s Make Friends on Joitter

Joitter is a social networking app for making friends.

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

The first line contains two integers $N,M$. The next $M$ lines each contain two integers $A_i,B_i$.

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

#### 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)$. | Subtask ID | $N\le $ | Score | |:-:|:-:|:-:| | $1$ | $50$ | $1$ | | $2$ | $2\times 10^3$ | $16$ | | $3$ | None | $83$ | #### Notes This problem is translated from Day 2 T2 “ジョイッターで友だちをつくろう” of [The 19th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html), [T2 ジョイッターで友だちをつくろう](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day2/joitter2-en.pdf). Translated by ChatGPT 5