#3275. 「JOISC 2020 Day2」有趣的 Joitter 交友

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Chanis

题目描述

题目译自 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 天开始,活动结束后每个用户关注其他用户数量和的最大值是多少。

样例

样例输入 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 关注了用户 3 。在这天活动结束的话,没有任何其他用户会关注其他人。所以总和是 2

第三天,用户 3 关注了用户 2 。在这天活动结束的话,用户 1 会关注用户 3 。所以总和是 4 ,并且它是总和的可能最大值。

第四天,用户 1 关注了用户 3 。在这天活动结束的话,没有任何其他用户会关注其他人。所以总和是 4

第五天,用户 3 关注了用户 4 。在这天活动结束的话,没有任何其他用户会关注其他人。所以总和是 5

第六天,用户 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

数据范围与提示

对于所有数据, 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)

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

子任务编号 附加限制 分值
1 N\le 50 1
2 N\le 2\times 10^3 16
3 无附加限制 83