配点 : $400$ 点

問題文

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

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

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

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

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

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

0
0
4
5
6

例えば、$1$ から $3$ 番目の橋が崩落したとき、$(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