题目描述

$N$ 個の島と $M$ 本の橋があります。

$i$ 番目の橋は $A_i$ 番目の島と $B_i$ 番目の島を繋いでおり、双方向に行き来可能です。

はじめ、どの $2$ つの島についてもいくつかの橋を渡って互いに行き来できます。

調査の結果、老朽化のためこれら $M$ 本の橋は $1$ 番目の橋から順に全て崩落することがわかりました。

「いくつかの橋を渡って互いに行き来できなくなった $2$ つの島の組 $(a,\ 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$ bit整数型に収まらない場合があることに注意すること。

题目大意

给定一个 $n$ 个点，$m$ 条边的无向图，

现在每次删除一条仍未被删除的边，共删除 $m$ 次。（每次删除操作时给定边的编号）

定义 $D(x,y)$ 表示 $x$ 和 $y$ 是否不能连通

对于每一次删除操作后，输出

注意答案可能不在int范围内

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

0
0
4
5
6

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

8
9
12
14
15

2 1
1 2

1

提示

制約

• 入力は全て整数である。
• $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$ である。

Sample Explanation 1

例えば、$1$ から $3$ 番目の橋が崩落したとき、$(1,\ 2),\ (1,\ 3),\ (2,\ 4),\ (3,\ 4)$ の島の組について行き来できなくなるので不便さは $4$ です。