AT_abc120_d [ABC120D] Decayed Bridges

题目描述

有 $N$ 个岛屿和 $M$ 座桥。

第 $i$ 座桥连接着第 $A_i$ 个岛屿和第 $B_i$ 个岛屿，可以双向通行。

一开始，任意两个岛屿之间都可以通过若干座桥互相到达。

经过调查，发现由于老化，这 $M$ 座桥将会按照编号从 $1$ 到 $M$ 的顺序依次坍塌。

我们将“无法通过若干座桥互相到达的两个岛屿的有序对 $(a, b)$（$a < b$）的数量”称为不便度。

请对于每个 $i$（$1 \leq i \leq M$），求出第 $i$ 座桥坍塌后立刻的不便度。

输入格式

输入以如下格式从标准输入给出：

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

输出格式

请按照 $i = 1, 2, ..., M$ 的顺序，输出第 $i$ 座桥坍塌后立刻的不便度。注意，答案可能超出 $32$ 位整数范围。

样例 1

输入

4 5
1 2
3 4
1 3
2 3
1 4

输出

0
0
4
5
6

样例 2

输入

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

输出

8
9
12
14
15

样例 3

输入

2 1
1 2

输出

1

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• 所有 $(A_i, B_i)$ 的组合均不相同。
• 初始状态下不便度为 $0$。

样例解释 1

例如，当第 $1$ 到第 $3$ 座桥坍塌时，无法互相到达的岛屿对为 $(1, 2), (1, 3), (2, 4), (3, 4)$，所以不便度为 $4$。

由 ChatGPT 4.1 翻译