{"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刚刚在他的右口袋里找到了一个有$n$个顶点且没有边的无向简单图(也就是说,这是一个有$n$个孤立顶点的图),其中顶点从1到$n$编号。现在他想对这个图执行$q$次以下两种操作中的一种:\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003e\u003cvar\u003e1\u003c/var\u003e \u003cvar\u003ea\u003c/var\u003e \u003cvar\u003eb\u003c/var\u003e -- 连接第$a$个顶点和第$b$个顶点的边。保证在此操作之前,不存在直接连接顶点$a$和$b$的边。\u003c/li\u003e\n \u003cli\u003e\u003cvar\u003e2\u003c/var\u003e \u003cvar\u003ek\u003c/var\u003e -- 回答以下查询:在向图中添加$k$条新边后,可能的连通分量数的最小值和最大值分别是多少。请注意,在添加$k$条边后,图必须仍然是一个简单图,而且此查询不会修改图本身。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e请帮助DreamGrid找到第二种操作的每个结果。回想一下,简单图是指没有自环或多重边的图。\u003c/p\u003e\n\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cp\u003e有多个测试用例。输入的第一行是一个整数$T$,表示测试用例的数量。对于每个测试用例:\u003c/p\u003e\n\n\u003cp\u003e第一行包含两个整数$n$和$q$($1 \\le n \\le 10^5$,$1 \\le q \\le 2 \\times 10^5$),表示顶点数和操作数。\u003c/p\u003e\n\n\u003cp\u003e接下来的$q$行,第$i$行首先包含一个整数$p_i$($p_i \\in \\{1, 2\\}$),表示第$i$个操作的类型。\u003c/p\u003e\n\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003e如果$p_i \u003d 1$,则后跟两个整数$a_i$和$b_i$($1 \\le a_i, b_i \\le n$,$a_i \\ne b_i$),表示第一种操作。保证在此操作之前,不存在直接连接顶点$a$和$b$的边。\u003c/li\u003e\n \u003cli\u003e如果$p_i \u003d 2$,则后跟一个整数$k_i$($0 \\le k_i \\le \\frac{n(n-1)}{2}$),表示第二种操作。保证向图中添加$k_i$条边后,图仍然是一个简单图。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e保证所有测试用例中$n$的总和不超过$10^6$,$q$的总和不超过$2 \\times 10^6$。\u003c/p\u003e\n\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cp\u003e对于第二种操作,输出一行,包含两个用空格分隔的整数,表示此查询中可能的连通分量数的最小值和最大值。\u003c/p\u003e\n\n\u003ch4\u003e示例\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"}}]}