AdditionalFile3275.zip

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

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 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
2
4
4
5
9

第一天，用户 $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

输出

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$

P7212 [JOISC 2020] ジョイッターで友だちをつくろう

题目背景

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$ 天之后的关注总数。

输入输出样例 #1

输入 #1

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

输出 #1

1
2
4
4
5
9

输入输出样例 #2

输入 #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

说明/提示

子任务

对于 $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)$。

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

说明

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