Joitter 是一个流行的社交媒体，你可以在上面与朋友分享你的记忆。

在 Joitter 中，你可以关注其他用户。例如，当用户 $a$ 关注另一个用户 $b$ 时，用户 $a$ 可以在时间线上阅读用户 $b$ 的动态。在这种情况下，用户 $b$ 可能会回关用户 $a$，也可能不会。然而，用户 $a$ 不可能关注他/她自己，也不可能多次关注同一个用户 $b$。

有 $N$ 个用户，编号为用户 $1, \text{用户 } 2, \dots, \text{用户 } N$，他们已经开始使用 Joitter。起初，他们都没有关注任何其他用户。

从现在开始，在 $M$ 天内，会发生以下关注事件：在第 $i$ 天，用户 $A_i$ 关注用户 $B_i$ ($1 \le i \le M$)。

Joitter 的官方计划在 $M$ 天内的某一天举办一次社交交流活动。社交交流活动的过程如下：

1. 选择一个用户。我们将选定的用户称为 $x$。
2. 选择一个此时正被 $x$ 关注的用户。我们将选定的用户称为 $y$。
3. 选择一个用户 $z$，满足：$z$ 与 $x$ 不同，$x$ 没有关注 $z$，$y$ 正在关注 $z$，且 $z$ 正在关注 $y$。
4. $x$ 关注 $z$。
5. 重复上述过程，直到无法再选择出满足条件的元组 $(x, y, z)$ 为止。

官方尚未决定何时举办社交交流活动。因此，他们想知道，对于每一天 $i$ ($1 \le i \le M$)，如果社交交流活动在第 $i$ 天的关注事件发生后立即举行，那么活动结束后所有用户关注的总人数的最大值是多少。我们假设社交交流活动在下一天的关注事件发生前结束。

编写一个程序，给定用户数量和 $M$ 天内的关注事件，计算对于每一天 $i$ ($1 \le i \le M$)，如果社交交流活动在第 $i$ 天的关注事件发生后立即举行，活动结束后所有用户关注的总人数的最大值。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N \ M$ $A_1 \ B_1$ $\vdots$ $A_M \ B_M$

输出格式

向标准输出写入 $M$ 行。在第 $i$ 行 ($1 \le i \le M$)，输出如果社交交流活动在第 $i$ 天的关注事件发生后立即举行，活动结束后所有用户关注的总人数的最大值。

数据范围

• $2 \le N \le 100\,000$
• $1 \le M \le 300\,000$
• $1 \le A_i \le N$ ($1 \le i \le M$)
• $1 \le B_i \le N$ ($1 \le i \le M$)
• $A_i \neq B_i$ ($1 \le i \le M$)
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \le i < j \le M$)

子任务

1. (1 分) $N \le 50$
2. (16 分) $N \le 2000$
3. (83 分) 无附加限制

样例

样例输入 1

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

样例输出 1

1
2
4
4
5
9

说明

• 第 1 天，用户 1 关注用户 2。在当天举行的社交交流活动中，没有人会关注其他人，因此总人数为 1。
• 第 2 天，用户 2 关注用户 3。在当天举行的社交交流活动中，没有人会关注其他人，因此总人数为 2。
• 第 3 天，用户 3 关注用户 2。在当天举行的社交交流活动中，用户 1 会关注用户 3。在这种情况下，总人数为 4，这是总人数可能达到的最大值。
• 第 4 天，用户 1 关注用户 3。在当天举行的社交交流活动中，没有人会关注其他人，因此总人数为 4。
• 第 5 天，用户 3 关注用户 4。在当天举行的社交交流活动中，没有人会关注其他人，因此总人数为 5。
• 第 6 天，用户 4 关注用户 3。在当天举行的社交交流活动中，用户 1 会关注用户 4，用户 2 会关注用户 4，用户 4 会关注用户 2。在这种情况下，总人数为 9，这是总人数可能达到的最大值。

样例输入 2

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

样例输出 2

1
2
3
4
5
7
11
17
25
30