学步园

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int maxn = 101000;
int sum[maxn*2],fa[maxn],tot[maxn*2];
int n,Q;
set<int> son[maxn*2];
int find(int u){
if(fa[u]==0){
    return u;
}
int father=find(fa[u]);
 if(father!=fa[u]){
 son[fa[u]].erase(u);
 son[father].insert(u);
 fa[u]=father;
 }
return father;
}
int main()
{
 while(scanf("%d %d",&n,&Q)!=EOF ){
    for(int i=1;i<=n;i++){
    fa[i]=i+maxn; fa[maxn+i]=0;
    son[maxn+i].clear(); son[maxn+i].insert(i);
    sum[maxn+i]=i; tot[maxn+i]=1;
    }
    while(Q--){
        int cmd,p,q;
        scanf("%d",&cmd);
        if(cmd==1){
            scanf("%d %d",&p,&q);
            int x=find(p),y=find(q);
            if(x!=y){
                fa[x]=y;
                sum[y]+=sum[x];  tot[y]+=tot[x];
                tot[x]=0; sum[x]=0;
            }
        }
       else if(cmd==3){
         scanf("%d",&p);
         printf("%d %d\n",tot[find(p)],sum[find(p)]);
       }
       else if(cmd==2){
         scanf("%d %d",&p,&q);
         int x=find(p),y=find(q);
         if(x!=y){
               set<int> ::iterator iter;
               for(iter=son[p].begin();iter!=son[p].end();iter++){
                     fa[*iter]=x;
               }
               son[p].clear();
               fa[p]=y;
               sum[x]-=p; tot[x]--;
               sum[y]+=p; tot[y]++;
         }
       }
    }
 }
 return 0;
}