记录编号	34659	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.695 s
提交时间	2011-12-26 22:10:35	内存使用	2.30 MiB

#include <cstdio>
using namespace std;
const int MAXN=30003;
int OrderNumber;
char OrderType;
class Ele
{
public:
	int Prev,Count;
}Names[MAXN];
int path[30002];
void Init()
{
int i;
	for(i=1;i<=30000;i++)
	{
		Names[i].Prev=i;
		Names[i].Count=1;
	}
}
int Abs(int obj)
{
	return (obj>0?obj:-obj);
}
int FindRoot(int obj)
{
int i,Root=0;
	if(Names[obj].Prev==obj)
		return obj;
	else
		Root=FindRoot(Names[obj].Prev);
	path[obj]+=path[Names[obj].Prev];
	Names[obj].Prev=Root;
	return Root;
}
void SetUnion(int o1,int o2)
{
int R1,R2;
	R1=FindRoot(o1);
	R2=FindRoot(o2);
	Names[R2].Prev=Names[R1].Prev;
	path[o2]+=Names[R1].Count;
	Names[R1].Count+=Names[R2].Count;
}
int main()
{
freopen("galaxy.in","r",stdin);
freopen("galaxy.out","w",stdout);
int i,j,k,l,T1,T2,R1,R2;
bool bo=false;
	scanf("%d",&OrderNumber);
	Init();
	for(k=1;k<=OrderNumber;k++)
	{
		scanf("%c%c%d%d",&OrderType,&OrderType,&i,&j);
		R1=FindRoot(i);
		R2=FindRoot(j);
		if(OrderType=='M')
			SetUnion(R1,R2);
		else
		{
			if(R1!=R2)
				printf("-1\n");
			else
				printf("%d\n",Abs(path[i]-path[j])-1);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}