Decayed Bridges

题目描述

有 $N$ 个岛屿和 $M$ 座桥。 第 $i$ 座桥双向连接第 $A_i$ 个和第 $B_i$ 个岛屿。 最初，我们可以利用这些桥在任意两座岛屿之间来回通行。 然而，调查结果显示这些桥会由于老化而全部倒塌，倒塌顺序为从第 1 座桥到第 $M$ 座桥。 记不便程度为无法再通过剩余桥梁在第 $a$ 个和 $b$ 个岛屿之间通行的岛屿对 $(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 位整数类型表示。

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

0
0
4
5
6

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

8
9
12
14
15

2 1
1 2

1

提示

输入中的所有数值都是整数。 $2 \leq N \leq 10^5$ $1 \leq M \leq 10^5$ 1 \leq A_i &lt; B_i \leq N 所有对 $(A_i, B_i)$ 都是互不相同的。 初始时不便程度为 $0$。例如，当第 1 到第 3 座桥已经倒塌时，不便程度为 $4$，因为我们无法再在以下对之间通行：$(1, 2), (1, 3), (2, 4)$ 和 $(3, 4)$。

标签: AtCoder|abc120D

来源

AtCoder|abc120D