题干：

DreamGrid has just found an undirected simple graph with  vertices and no edges (that's to say, it's a graph with  isolated vertices) in his right pocket, where the vertices are numbered from 1 to . Now he would like to perform  operations of the following two types on the graph:

  • 1 a b -- Connect the -th vertex and the -th vertex by an edge. It's guaranteed that before this operation, there does not exist an edge which connects vertex  and  directly.
  • 2 k -- Find the answer for the query: What's the minimum and maximum possible number of connected components after adding  new edges to the graph. Note that after adding the  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 , indicating the number of test cases. For each test case:

The first line contains two integers  and  (, ), indicating the number of vertices and the number of operations.

For the following  lines, the -th line first contains an integer  (), indicating the type of the -th operation.

  • If , two integers  and  follow (, ), indicating an operation of the first type. It's guaranteed that before this operation, there does not exist an edge which connects vertex  and  directly.
  • If , one integer  follows (), indicating an operation of the second type. It's guaranteed that after adding  edges to the graph, the graph is still possible to be a simple graph.

 

It's guaranteed that the sum of  in all test cases will not exceed , and the sum of  in all test cases will not exceed .

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

解题报告：

以连通块中元素个数为权值，建立线段树，维护三个变量，分别是cnt（这样的连通块的数量），sum（连通块的总的点数），pfh（各连通块之间点数的平方和）（注意不是和的平方）

cnt代表连通块数量，tot_ret代表当前状态下的图，在不增长连通块个数的前提下，可以加的边数。

所以对于最小值很显然。

对于最大值，首先减去块内连的边，然后去线段树查询剩下的边怎么加，首先填连通块元素大小大的，这样也就是类似查询第k大，查到叶子结点，再判断 块中元素为tree[cur].l的 块 我需要多少个 返***去，就行了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int n,q,cnt,f[MAX];
ll tot_ret,ret[MAX],num[MAX];
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}
struct TREE {
	int l,r;
	ll cnt,sum;
	ll pfh;
} tree[MAX<<2];
void pushup(int cur) {
	tree[cur].cnt = tree[cur*2].cnt + tree[cur*2+1].cnt;
	tree[cur].sum = tree[cur*2].sum + tree[cur*2+1].sum;
	tree[cur].pfh = tree[cur*2].pfh + tree[cur*2+1].pfh;
}
void build(int l,int r,int cur) {
	tree[cur].l=l;tree[cur].r=r;
	if(l == r) {
		tree[cur].pfh = tree[cur].sum = tree[cur].cnt = (l==1?n:0);
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,cur*2);
	build(mid+1,r,cur*2+1);
	pushup(cur);
}
void update(int cur,ll tar,ll val) {
	if(tree[cur].l == tree[cur].r) {
		tree[cur].cnt += val;// 连通块元素数量为tar的连通块的数量。 
		tree[cur].sum += val*tar;
		tree[cur].pfh += val*tar*tar;
		return;
	}
	int mid = (tree[cur].l+tree[cur].r)>>1;
	if(tar<=mid) update(cur*2,tar,val);
	else update(cur*2+1,tar,val); 
	pushup(cur);
}
ll query(int cur,ll k,int sum) {
	if(tree[cur].l == tree[cur].r) {
		ll l=1,r=tree[cur].cnt,mid;
		mid=(l+r)>>1;
		while(l<r) {
			mid=(l+r)>>1;
			if(mid*(mid-1)/2*tree[cur].l*tree[cur].l + mid*tree[cur].l*sum >= k) r=mid;
			else l = mid+1;
		}
		return l;
	}
	int mid = (tree[cur].l+tree[cur].r)>>1;
	ll tmp = (tree[cur*2+1].sum * tree[cur*2+1].sum - tree[cur*2+1].pfh)/2 + tree[cur*2+1].sum * sum ;
	if(tmp < k)
		return tree[cur*2+1].cnt + query(cur*2,k-tmp,sum+tree[cur*2+1].sum);
	else return query(cur*2+1,k,sum);
}
ll cal(ll k) {
	if(k<=tot_ret) return cnt;
	k-=tot_ret;
	ll tmp = query(1,k,0);
	return cnt-tmp+1;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&q);
		for(int i = 1; i<=n; i++) f[i] = i,num[i] = 1,ret[i] = 0;
		tot_ret=0,cnt=n;//cnt记录连通块数 
		build(1,n,1);
		while(q--) {
			int op;
			scanf("%d",&op);
			if(op == 1) {
				int a,b;
				scanf("%d%d",&a,&b);
				a=getf(a),b=getf(b);
				if(a==b) {
					ret[a]--;
					tot_ret--;
					continue;
				}
				if(num[a] > num[b]) swap(a,b);//让b是边多的
				update(1,num[a],-1);
				update(1,num[b],-1);
				f[a]=b;//按秩合并到大集合
				tot_ret += num[a]*num[b]-1;cnt--;
				ret[b]=ret[a]+ret[b] + num[a]*num[b]-1;
				num[b]+=num[a];
				ret[a]=num[a]=0;
				update(1,num[b],1);			
			}
			else {
				ll k;
				scanf("%lld",&k);
				ll minn = max(1LL,cnt-k);
				ll maxx = cal(k);
				printf("%lld %lld\n",minn,maxx);
			}			
		}
	}
	return 0 ;
}