题目描述

题目译自 JOISC 2020 Day2 T2「ジョイッターで友達をつくろう / Making Friends on Joitter is Fun」

$\texttt{Joitter}$ 是一款社交软件，你可以在这里和你的朋友分享你的高光时刻。

在 $\texttt{Joitter}$ 中，你可以关注别的用户。举例来说，当用户 $a$ 关注了另外一个用户 $b$ ，用户 $a$ 可以在时间轴上阅读用户 $b$ 的帖子。在这种情况下，用户 $b$ 有可能关注用户 $a$ ，也可能不关注用户 $a$ 。当然，用户 $a$ 不能关注 Ta 自己或者关注用户 $b$ 超过一次。

一共有 $N$ 个用户已经开始使用 $\texttt{Joitter}$ ，一开始他们没有关注任何其他用户。

从现在起，持续 $M$ 天，在第 $i$ 天会发生用户 $A_i$ 关注用户 $B_i$ 的事件（$1 \le i \le M$）。

$\texttt{Joitter}$ 官方正在计划在这 $M$ 天中举行一场活动，这场活动有如下的步骤：

1. 选择一个用户 $x$ 。
2. 同时选择一个被 $x$ 关注的用户 $y$ 。
3. 选择一个用户 $z$ ，要求满足 $z$ 不是 $x$ ，$x$ 没有关注 $z$ ，且 $y$ 和 $z$ 互相关注。
4. 让 $x$ 关注 $z$
5. 重复上述步骤，直到无法选出三元组 $(x,y,z)$

$\texttt{Joitter}$ 官方仍然还没有决定何时开始举办这个活动。所以他们想要知道，$\forall i \in [1,m]$，若活动在第 $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

数据范围与提示

对于所有数据，$2\le N\le 10^5,1\le M\le 3\times 10^5$，保证：

• $1\le A_i,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\lt j\le M)$。

详细子任务及附加限制如下表：