{"problem":{"name":"Decayed Bridges","description":{"content":"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. Ho","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc120_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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$.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc120_d","tags":[],"sample_group":[["4 5\n1 2\n3 4\n1 3\n2 3\n1 4","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)$."],["6 5\n2 3\n1 2\n5 6\n3 4\n4 5","8\n9\n12\n14\n15"],["2 1\n1 2","1"]],"created_at":"2026-03-03 11:01:14"}}