题目描述

有 $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$ 位整数类型。

示例输入 1

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

示例输出 1

0
0
4
5
6

例如，当第一到第三条桥梁坍塌时，不便之处为 $4$，因为我们无法再在岛屿对 $(1, 2), (1, 3), (2, 4)$ 和 $(3, 4)$ 之间旅行。

示例输入 2

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

示例输出 2

8
9
12
14
15

示例输入 3

2 1
1 2

示例输出 3

1