Tenemos ~n (1 \le n \le 10^5)~ islas y ~m (1 \le m \le 10^5)~ puentes. El ~i~-ésimo puente conecta la ~a_i~-ésima y la ~b_i~-ésima isla bidireccionalmente.

Sin embargo, los resultados de un estudio muestran que todos estos puentes se derrumbarán debido al envejecimiento, en el orden del primer puente al ~m~-ésimo puente.

Sea la inconveniencia igual al número de pares de islas ~(a, b)~ con ~a < b~, de tal manera que ya no podemos viajar entre la ~a~-ésima isla y la ~b~-ésima isla mediante los puentes que quedan. Para cada ~i (1 \le i \le m)~ calcular el inconveniente justo después de que el ~i~-ésimo puente se derrumbe.

La inconveniencia es inicialmente igual a 0.

Entrada

La entrada se da en el siguente formato:

~n~ ~m~

~a_1~ ~b_1~

~a_2~ ~b_2~

~\vdots~

~a_m~ ~b_m~

Salida

En el orden ~i=1, 2, \ldots, m~ imprima la inconveniencia justo después de que colapse el ~i~-ésimo puente.

Ejemplo de Entrada 1

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

Ejemplo de Salida 1

0
0
4
5
6

Ejemplo de Entrada 2

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

Ejemplo de Salida 2

8
9
12
14
15

Ejemplo de Entrada 3

2 1
1 2

Ejemplo de Salida 3

1