题目描述

海面上有 $N$ 座岛屿，编号为 $1$ 到 $N$，岛屿之间共有 $M$ 座桥。第 $i$ 座桥连接岛屿 $A_i$ 和岛屿 $B_i$，可以双向通行。最初，任意两座岛屿之间都可以通过若干座桥互相到达。

小婷在一次安全调查中发现，由于长期老化，这些桥将依次倒塌：先倒塌第 $1$ 座桥，再倒塌第 $2$ 座桥，直到第 $M$ 座桥。已经倒塌的桥不能再通行。

在任意时刻，把不能通过剩余桥梁互相到达的一对岛屿 $(a,b)$（其中 $a<b$）称为一对“不便岛屿”。当前所有不便岛屿对的数量称为“不便度”。

请对每个 $i=1,2,\ldots,M$，计算第 $i$ 座桥刚刚倒塌之后的不便度。答案可能超过 $32$ 位整数范围。

输入格式

第一行输入两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行输入两个整数 $A_i,B_i$，表示第 $i$ 座桥连接的两座岛屿。

输出格式

输出 $M$ 行。第 $i$ 行输出第 $i$ 座桥倒塌之后的不便度。

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

0
0
4
5
6

样例说明 #1

前三座桥倒塌后，不能互相到达的岛屿对为 $(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

样例说明 #3

唯一的一座桥倒塌后，两座岛屿不能互相到达，不便度为 $1$。

数据范围与约定

$2\le N\le10^5$，$1\le M\le10^5$，$1\le A_i<B_i\le N$。所有 $(A_i,B_i)$ 互不相同，初始状态的不便度为 $0$。输入中的所有数均为整数。