记录编号	58565	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.814 s
提交时间	2013-04-22 20:14:27	内存使用	3.14 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
/*
ifstream fi("galaxy.in");
ofstream fo("galaxy.out");
*/
int T;
class set//并查集的集合C
{
public:
	int parent;
	int dis;//记录到最高点的距离即该集合中，这个元素之前有多少个元素
	int count;//表示该元素所在集合中元素的总个数
}C[30001];
void makeset(int x)//集
{
	C[x].parent=x;
	C[x].dis=0;
	C[x].count=1;
}
int findset(int x)
{
	if(C[x].parent==x)return x;
	int y=findset(C[x].parent);
	C[x].dis=C[x].dis+C[C[x].parent].dis;
	C[x].parent=y;
	return C[x].parent;
}
void merge(int x,int y)//并
{
	int a=findset(x),b=findset(y);
	C[a].parent=b;
	C[a].dis=C[b].count;
	C[b].count+=C[a].count;
}
int main()
{
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	char ch;
	int c,d;
	scanf("%d",&T);//fi>>T;
	for(int i=1;i<=30000;i++)makeset(i);
	for(int i=1;i<=T;i++)
	{
		scanf("%c%c",&ch,&ch);
		scanf("%d%d",&c,&d);
		//fi>>ch>>c>>d;
		if(ch=='M')merge(c,d);
		else 
		{
			if(findset(c)==findset(d))printf("%d\n",(int)abs(C[c].dis-C[d].dis)-1);//fo<<abs(C[c].dis-C[d].dis)-1<<endl;
			else printf("-1\n");//fo<<"-1"<<endl;
		}
	}
	return 0;
}