D - 衰败的桥梁

分数：$400$分

问题描述

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

第$i$座桥梁双向连接第$A_i$座和第$B_i$座岛屿。

最初，我们可以通过其中一些桥梁在任意两个岛屿之间旅行。

然而，一项调研结果显示，由于老化，这些桥梁将会全部倒塌，倒塌的顺序是从第一座桥梁到第$M$座桥梁。

定义不便之处为对于某两座岛屿$(a, b)$ （$a < b$)，我们不能通过剩余的桥梁之中的某些桥梁旅行到第$a$座和第$b$座岛屿之间的数量。

对于每个$i$ ($1 \leq i \leq M$)，找到第$i$座桥梁倒塌后的不便之处。

约束条件

• 输入中的所有值均为整数。
• $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$。

输入

输入的格式如下：

$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

例如，当第一到第三座桥梁倒塌时，不便之处为$4$，因为我们无法再通过$(1, 2), (1, 3), (2, 4)$和$(3, 4)$这些对进行旅行。

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

8
9
12
14
15

2 1
1 2

1