题目描述

There are $N$ islands and $M$ bridges.

The $i$-th bridge connects the $A_i$-th and $B_i$-th islands bidirectionally.

Initially, we can travel between any two islands using some of these bridges.

However, the results of a survey show that these bridges will all collapse because of aging, in the order from the first bridge to the $M$-th bridge.

Let the inconvenience be the number of pairs of islands $(a, b)$ ($a \lt b$) such that we are no longer able to travel between the $a$-th and $b$-th islands using some of the bridges remaining.

For each $i$ $(1 \leq i \leq M)$, find the inconvenience just after the $i$-th bridge collapses.

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

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

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

然而，一项调查结果显示，这些桥都会因为老化而倒塌，倒塌的顺序是从第一座桥到第 $M$ 座桥。

假设不方便是 $(a, b)$ （ $a \lt 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

样例输入 #1

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

样例输出 #1

0
0
4
5
6

样例 #2

样例输入 #2

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

样例输出 #2

8
9
12
14
15

样例 #3

样例输入 #3

2 1
1 2

样例输出 #3

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$ 解释

例如，当第一座至第三座桥梁倒塌时，由于我们无法再在 $(1, 2), (1, 3), (2, 4)$ 和 $(3, 4)$ 这两对桥梁之间通行，因此带来的不便为 $4$ 。