{"problem":{"name":"Graph Destruction","description":{"content":"Given is an undirected graph with $N$ vertices and $M$ edges.   Edge $i$ connects Vertices $A_i$ and $B_i$. We will erase Vertices $1, 2, \\ldots, N$ one by one.   Here, erasing Vertex $i$ means deleti","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc229_e"},"statements":[{"statement_type":"Markdown","content":"Given is an undirected graph with $N$ vertices and $M$ edges.  \nEdge $i$ connects Vertices $A_i$ and $B_i$.\nWe will erase Vertices $1, 2, \\ldots, N$ one by one.  \nHere, erasing Vertex $i$ means deleting Vertex $i$ and all edges incident to Vertex $i$ from the graph.\nFor each $i=1, 2, \\ldots, N$, how many connected components does the graph have when vertices up to Vertex $i$ are deleted?\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min(\\frac{N(N-1)}{2} , 2 \\times 10^5 )$\n*   $1 \\leq A_i \\lt B_i \\leq N$\n*   $(A_i,B_i) \\neq (A_j,B_j)$ if $i \\neq j$.\n*   All values in input are integers.\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":"abc229_e","tags":[],"sample_group":[["6 7\n1 2\n1 4\n1 5\n2 4\n2 3\n3 5\n3 6","1\n2\n3\n2\n1\n0\n\n![image](https://img.atcoder.jp/ghi/3320212a9093132a80105bf02feeb195.png)  \nThe figure above shows the transition of the graph."],["8 7\n7 8\n3 4\n5 6\n5 7\n5 8\n6 7\n6 8","3\n2\n2\n1\n1\n1\n1\n0\n\nThe graph may be disconnected from the beginning."]],"created_at":"2026-03-03 11:01:14"}}