{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid has just found an undirected simple graph with $n$ vertices and no edges (that\u0027s to say, it\u0027s a graph with $n$ isolated vertices) in his right pocket, where the vertices are numbered from 1 to $n$. Now he would like to perform $q$ operations of the following two types on the graph:\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003e\u003cvar\u003e1\u003c/var\u003e \u003cvar\u003ea\u003c/var\u003e \u003cvar\u003eb\u003c/var\u003e -- Connect the $a$-th vertex and the $b$-th vertex by an edge. It\u0027s guaranteed that before this operation, there does not exist an edge which connects vertex $a$ and $b$ directly.\u003c/li\u003e\n \u003cli\u003e\u003cvar\u003e2\u003c/var\u003e \u003cvar\u003ek\u003c/var\u003e -- Find the answer for the query: What\u0027s the minimum and maximum possible number of connected components after adding $k$ new edges to the graph. Note that after adding the $k$ edges, the graph must still be a simple graph, and the query does NOT modify the graph.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003ePlease help DreamGrid find the answer for each operation of the second type. Recall that a simple graph is a graph with no self loops or multiple edges.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers $n$ and $q$ ($1 \\le n \\le 10^5$, $1 \\le q \\le 2 \\times 10^5$), indicating the number of vertices and the number of operations.\u003c/p\u003e\n\n\u003cp\u003eFor the following $q$ lines, the $i$-th line first contains an integer $p_i$ ($p_i \\in \\{1, 2\\}$), indicating the type of the $i$-th operation.\n\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eIf $p_i \u003d 1$, two integers $a_i$ and $b_i$ follow ($1 \\le a_i, b_i \\le n$, $a_i \\ne b_i$), indicating an operation of the first type. It\u0027s guaranteed that before this operation, there does not exist an edge which connects vertex $a$ and $b$ directly.\u003c/li\u003e\n \u003cli\u003eIf $p_i \u003d 2$, one integer $k_i$ follows ($0 \\le k_i \\le \\frac{n(n-1)}{2}$), indicating an operation of the second type. It\u0027s guaranteed that after adding $k_i$ edges to the graph, the graph is still possible to be a simple graph.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ in all test cases will not exceed $10^6$, and the sum of $q$ in all test cases will not exceed $2 \\times 10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each operation of the second type output one line containing two integers separated by a space, indicating the minimum and maximum possible number of connected components in this query.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e1\n5 5\n1 1 2\n2 1\n1 1 3\n2 1\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n2 3\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}