DreamGrid has just found an undirected simple graph with $n$ vertices and no edges (that's to say, i

DreamGrid has just found an undirected simple graph with $n$ vertices and no edges (that’s to say, it’s 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:

1 a b – Connect the $a$-th vertex and the $b$-th vertex by an edge. It’s guaranteed that before this operation, there does not exist an edge which connects vertex $a$ and $b$ directly.
2 k – Find the answer for the query: What’s 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.
Please 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.

Input
There are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case:

The 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.

For the following $q$ lines, the $i$-th line first contains an integer $p_i$ ( p i ∈ { 1 , 2 } p_i in {1, 2} pi​∈{1,2}), indicating the type of the $i$-th operation.

If $p_i=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’s guaranteed that before this operation, there does not exist an edge which connects vertex $a$ and $b$ directly.
If $p_i=2$, one integer $k_i$ follows ($0\le k_i\le \frac{n(n-1)}{2}$), indicating an operation of the second type. It’s guaranteed that after adding $k_i$ edges to the graph, the graph is still possible to be a simple graph.
It’s 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$.

Output
For 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.

Sample Input
1
5 5
1 1 2
2 1
1 1 3
2 1
2 3
Sample Output
3 3
2 3
1 2

最后

以上就是任性保温杯为你收集整理的DreamGrid has just found an undirected simple graph with $n$ vertices and no edges (that's to say, i的全部内容，希望文章能够帮你解决DreamGrid has just found an undirected simple graph with $n$ vertices and no edges (that's to say, i所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。