
ZOJ Problem Set  4100
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:
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. InputThere 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.
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$. OutputFor 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 Input1 5 5 1 1 2 2 1 1 1 3 2 1 2 3 Sample Output3 3 2 3 1 2 Author: WANG, Yucheng Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 