Joitter 是一种流行的社交媒体，在这里你可以和你的朋友分享你的记忆。

在 Joitter 你可以关注其他人。如果用户 $a$ 关注了用户 $b$ ，用户 $a$ 就可以在时间轴上看到用户 $b$ 发送的信息。这种情况下，用户 $b$ 可能关注用户 $a$，也可能不关注用户 $a$。但是一个用户不能关注他自己。

Joitter 有 $N$ 个用户，编号为 $1$ 至 $N$ 。开始时没有任何一个用户关注其他人。

在之后的 $M$ 天里，每一天都会发生用户 $A_i$ 关注用户 $B_i$ 的事件。

Joitter 官方打算在 $M$ 天中举行一次线上交友活动。线上交友活动按照如下规则举行：

1. 选择一个用户，我们称之为用户 $x$ 。
2. 选择一个用户 $x$ 关注的用户，我们称之为用户 $y$。
3. 选择一个不为用户 $x$ 的用户 $z$, 使得用户 $y$ 与用户 $z$ 互相关注，且用户$x$ 未关注用户 $z$。
4. 用户 $x$ 关注用户 $z$。
5. 重复以上进程直至无法选出合法三元组 $(x,y,z)$。

Joitter 官方并未决定在哪一天举行活动，因此对于所有 $1 \le i \le M$，他们想要知道在第 $i$ 天的事件发生后举行交友活动，结束后至多能产生多少组关注关系。

输入格式

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

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

输出格式

$M$ 行，第 $i$ 行一个整数表示在第 $i$ 天的事件发生后举行交友活动，结束后至多能产生多少组关注关系。

样例一

input

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

output

1
2
4
4
5
9

explanation

第一天用户 $1$ 关注了用户 $2$，活动不产生任何关注关系，因此总数为 $1$ 。

第二天用户 $2$ 关注了用户 $3$，活动不产生任何关注关系，因此总数为 $2$ 。

第三天用户 $3$ 关注了用户 $2$，活动时用户 $1$ 关注了用户 $3$ ，因此总数为 $4$ 。

第四天用户 $1$ 关注了用户 $3$，活动不产生任何关注关系，因此总数为 $4$ 。

第五天用户 $3$ 关注了用户 $4$，活动不产生任何关注关系，因此总数为 $5$ 。

第六天用户 $4$ 关注了用户 $3$，活动时用户 $1$ 关注了用户 $4$，用户 $2$ 关注了用户 $4$，用户 $4$ 关注了用户 $2$，因此总数为 $9$ 。可以证明其为所有情况下的最大值。

样例二

input

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

output

1
2
3
4
5
7
11
17
25
30

数据范围

子任务1($1$分):$N \le 50$。

子任务2($16$分):$N \le 2000$。

子任务3($83$分):无特殊限制。

对于所有测试数据，满足$2 \le N \le 100000,1 \le M \le 300000,1 \le A_i,B_i \le N,A_i \neq B_i$。

保证用户 $a$ 不会多次关注用户 $b$。

时间限制:$\texttt{4S}$。

空间限制:$\texttt{1GB}$。