Problem Statement

There are $N$ islands and $M$ bridges.

The $i$-th bridge connects the $A_i$-th and $B_i$-th islands bidirectionally.

Initially, we can travel between any two islands using some of these bridges.

However, the results of a survey show that these bridges will all collapse because of aging, in the order from the first bridge to the $M$-th bridge.

Let the inconvenience be the number of pairs of islands $(a, b)$ ($a < b$) such that we are no longer able to travel between the $a$-th and $b$-th islands using some of the bridges remaining.

For each $i$ $(1 \leq i \leq M)$, find the inconvenience just after the $i$-th bridge collapses.

Constraints

• All values in input are integers.
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• All pairs $(A_i, B_i)$ are distinct.
• The inconvenience is initially $0$.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

In the order $i = 1, 2, ..., M$, print the inconvenience just after the $i$-th bridge collapses. Note that the answer may not fit into a $32$-bit integer type.