{"raw_statement":[{"iden":"problem statement","content":"There are $N$ islands and $M$ bridges.\nThe $i$\\-th bridge connects the $A_i$\\-th and $B_i$\\-th islands bidirectionally.\nInitially, we can travel between any two islands using some of these bridges.\nHowever, 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.\nLet 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.\nFor each $i$ $(1 \\leq i \\leq M)$, find the inconvenience just after the $i$\\-th bridge collapses."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq A_i < B_i \\leq N$\n*   All pairs $(A_i, B_i)$ are distinct.\n*   The inconvenience is initially $0$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_M$ $B_M$"},{"iden":"sample input 1","content":"4 5\n1 2\n3 4\n1 3\n2 3\n1 4"},{"iden":"sample output 1","content":"0\n0\n4\n5\n6\n\nFor example, when the first to third bridges have collapsed, the inconvenience is $4$ since we can no longer travel between the pairs $(1, 2), (1, 3), (2, 4)$ and $(3, 4)$."},{"iden":"sample input 2","content":"6 5\n2 3\n1 2\n5 6\n3 4\n4 5"},{"iden":"sample output 2","content":"8\n9\n12\n14\n15"},{"iden":"sample input 3","content":"2 1\n1 2"},{"iden":"sample output 3","content":"1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}