J11 例题-4 桥的坍塌

题目描述

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

第 $i$ 座桥连接着第 $A_i$ 个岛和 第 $B_i$ 个岛之间的双向交通。

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

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

不便指数是指有多少对岛屿 $(a,b)(a<b)$，使我们不能再使用剩余的一些桥梁在第 $a$ 个和第 $b$ 个岛屿之间旅行。

对于每个 $i(1 \le i \le M)$，找出第 $i$ 座桥倒塌后的不便指数。

输入格式

共 $M+1$ 行： 第一行两个个整数 $N,M$ ，表示岛屿和桥的数量； 接下来的 $M$ 行，每行两个整数 $A_i,B_i$ ，依次表示每座桥连接的岛屿的编号。

输出格式

共 $M$ 行一个整数，按照 $i=1,2,...,M$ 的顺序，输出第 $i$ 座桥刚倒塌时的不便。注意，答案可能是 $64$ 位的整数类型。

样例输入1

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

样例输出1

0
0
4
5
6

样例1解析

例如，当第一座到第三座桥倒塌时，由于我们不能再在 $(1,2)$、$(1,3)$、$(2,4)$ 和 $(3,4)$ 这几对桥之间旅行，所以不便之处就是4。

样例输入2

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

样例输出2

8
9
12
14
15

数据范围

对于 $100 \%$ 的数据：$2 \le N \le 10^5$，$1 \leq M \leq 10^5$，$1 \leq A_i < B_i \leq N$，$A_i \ne B_i$，不便指数初始为 $0$。