不便程度

题目描述

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

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

起初，任意两个岛之间都可以通过若干座桥互相往来。

调查结果表明，由于老化，这 $M$ 座桥将从第 $1$ 座桥开始依次全部崩塌。

把「无法通过若干座桥互相往来的两个岛的组 $(a, b)$（其中 $a \lt b$）的数量」称为不便程度。

对每个 $i$（$1 \le i \le 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

例如，当第 $1$ 到第 $3$ 座桥崩塌时，$(1, 2), (1, 3), (2, 4), (3, 4)$ 这些岛的组合无法互相往来，所以不便程度为 $4$。

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

8
9
12
14
15

2 1
1 2

1

数据范围

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