题目背景

Joitter 是一款交友软件。

题目描述

在 Joitter 你可以关注他人，但你不可以关注自己和关注他人两次，即如果关注他人多次只会算作一次。

共有 $N$ 名新用户，$M$ 天。

在第 $i$ 天，用户 $A_i$ 会关注用户 $B_i$。

同时在关注之后，会举办一场交友活动，活动内容如下：

1. 选择一个用户 $x$。
2. 选择一个被用户 $x$ 关注的用户 $y$。
3. 选择一个用户 $z$，要求 $z\not=x$，$x$ 未关注 $z$ 且 $y$ 和 $z$ 互关。
4. 让 $x$ 关注 $z$。
5. 重复 $1,2,3,4$，直到选不出合适的三元组 $(x,y,z)$。

您需要求出，对于每一个 $i$，第 $i$ 天过后的所有关注总数。

输入格式

第一行为两个整数 $N,M$。

接下来 $M$ 行，一行两个整数 $A_i,B_i$。

输出格式

输出共 $M$ 行，每一行一个数，第 $i$ 行表示经过第 $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

提示

子任务

对于 $100\%$ 的数据，保证 $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$，$(A_i,B_i)\not=(A_j,B_j)$。

说明

本题译自 第 19 回日本情報オリンピック　春季トレーニング合宿 Day 2 T2 ジョイッターで友だちをつくろう。