{"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\u003eBạn có biết gì về DFS, Depth First Search không? Ví dụ, sử dụng phương pháp này, bạn có thể xác định xem một đồ thị có kết nối hay không trong thời gian \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eO\u003c/i\u003e(\u003ci\u003eE\u003c/i\u003e)\u003c/span\u003e. Bạn thậm chí có thể đếm số thành phần kết nối trong cùng một thời gian.\u003c/p\u003e\u003cp\u003eBạn có biết gì về DSU, Disjoint Set Union không? Sử dụng cấu trúc dữ liệu này, bạn có thể xử lý các truy vấn như \"Thêm một cạnh vào đồ thị\" và \"Đếm số thành phần kết nối trong đồ thị\" một cách nhanh chóng.\u003c/p\u003e\u003cp\u003eVà bạn có biết cách giải quyết vấn đề Dynamic Connectivity không? Trong vấn đề này, bạn phải xử lý ba loại truy vấn một cách nhanh chóng: \u003c/p\u003e\u003col\u003e \u003cli\u003e Thêm một cạnh vào đồ thị \u003c/li\u003e\u003cli\u003e Xóa một cạnh khỏi đồ thị \u003c/li\u003e\u003cli\u003e Đếm số thành phần kết nối trong đồ thị \u003c/li\u003e\u003c/ol\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eLúc ban đầu, đồ thị là trống.\u003c/p\u003e\u003cp\u003eDòng đầu tiên của tệp chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e—số đỉnh và số truy vấn (\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). Tiếp theo là \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e dòng chứa các truy vấn, mỗi truy vấn trên một dòng. Có ba loại truy vấn: \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: thêm một cạnh giữa các đỉnh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. Đảm bảo rằng không có cạnh như vậy trong đồ thị vào thời điểm của truy vấn. \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: xóa một cạnh giữa các đỉnh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. Đảm bảo rằng cạnh này hiện diện trong đồ thị vào thời điểm của truy vấn. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e: đếm số thành phần kết nối trong đồ thị vào thời điểm của truy vấn. \u003c/li\u003e\u003c/ol\u003e Các đỉnh được đánh số từ \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e. Không có truy vấn nào sẽ có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e \u003d \u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. Đồ thị là vô hướng."}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eĐối với mỗi truy vấn \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\u0027, đầu ra số lượng thành phần kết nối trong đồ thị vào thời điểm của truy vấn trên một dòng duy nhất.\u003c/p\u003e"}},{"title":"Sample 1","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"}}]}