Problem Description

John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1...N。Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:

M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command. 

C X : Count the number of blocks under block X 

You are request to find out the output for each C operation.

 

Input

The first line contains integer P. Then P lines follow, each of which contain an operation describe above.

 

Output

Output the count for each C operations in one line.

 

Sample Input

 

Sample Output

这题也是带权并查集，设三个数组pre[i],num[i](代表i所在集合的数字总数),root[i]表示i下面的数字总数。每次移动时输入两个数a,b,因为移动过程中a所在的所有数都移动到b所在集合所有数的上面，所以令a的祖先t1的父亲为b的祖先t2，这样下面递归的时候，root[i]可以递归相加。

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<map>

#include<string>

using namespace std;

char s[10];

int pre[30005],num[30005],root[30005];

int find(int x)

{

	int temp;

	if(pre[x]==x)return x;

	temp=pre[x];

	pre[x]=find(pre[x]);

	root[x]+=root[temp];

	return find(pre[x]);

}

int main()

{

	int p,i,m,j,a,b,t1,t2;

	while(scanf("%d",&p)!=EOF)

	{

		for(i=0;i<=30005;i++){

			pre[i]=i;num[i]=1;root[i]=0;

		}

		while(p--)

		{

			scanf("%s",s);

			if(s[0]=='M'){

				scanf("%d%d",&a,&b);

				t1=find(a);t2=find(b);

				if(t1==t2)continue;

				pre[t1]=t2;

				root[t1]+=num[t2];

				num[t2]+=num[t1];

			}

			else if(s[0]=='C'){

				scanf("%d",&a);

				t1=find(a);

				printf("%d\n",root[a]);

			}

		}

	}

	return 0;

}