{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDo you know anything about DFS, Depth First Search? For example, using this method, you can determine whether a graph is connected or not in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eO\u003c/i\u003e(\u003ci\u003eE\u003c/i\u003e)\u003c/span\u003e time. You can even count the number of connected components in the same time.\u003c/p\u003e\u003cp\u003eDo you know anything about DSU, Disjoint Set Union? Using this data structure, you can process queries like \"Add an edge to the graph\" and \"Count the number of connected components in the graph\" fast.\u003c/p\u003e\u003cp\u003eAnd do you know how to solve Dynamic Connectivity Problem? In this problem, you have to process three types of queries fast: \u003c/p\u003e\u003col\u003e \u003cli\u003e Add an edge to the graph \u003c/li\u003e\u003cli\u003e Delete an edge from the graph \u003c/li\u003e\u003cli\u003e Count the number of connected components in the graph \u003c/li\u003e\u003c/ol\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eAt the first moment, the graph is empty.\u003c/p\u003e\u003cp\u003eThe first line of file contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e—number of vertices and number of queries (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 300 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eK\u003c/i\u003e ≤ 300 000\u003c/span\u003e). Next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e lines contain queries, one per line. There are three types of queries: \u003c/p\u003e\u003col\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e+ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e\u003c/span\u003e: add an edge between vertices \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. It is guaranteed that there is no such edge in the graph at the time of the query. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e- \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e\u003c/span\u003e: remove an edge between vertices \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. It is guaranteed that this edge is present in the graph at the time of the query. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e: count the number of connectivity components in the graph at the time of the query. \u003c/li\u003e\u003c/ol\u003e Vertices are numbered \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e. No query will have \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e \u003d \u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. The graph is undirected."}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\u0027 query, output the number of connectivity components in the graph at the time of the query on a single line.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 11\n?\n+ 1 2\n+ 2 3\n+ 3 4\n+ 4 5\n+ 5 1\n?\n- 2 3\n?\n- 4 5\n?\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1\n1\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}