Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4100
Vertices in the Pocket

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 \in \{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

Author: WANG, Yucheng
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status