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$

$⋮$

$a_m$ $b_m$

Salida

En el orden $i=1,2,\dots ,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