记录编号	124368	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	席一鸣	是否通过	通过
代码语言	C++	运行时间	2.834 s
提交时间	2014-10-03 15:03:36	内存使用	0.66 MiB

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
char t;
int m,q,a,b,f[30001],o[30001]={0},c[30001];
void r(int&d)
{
	char t=getchar();
	while(t<'0'||t>'9')
	  t=getchar();
	for(d=0;t>='0'&&t<='9';t=getchar())
	  d=(d<<3)+(d<<1)+t-'0';
}
int find(int n)
{
	int d;
	if(n==f[n])
	  return n;
	else
	{
		d=find(f[n]);
		o[n]+=o[f[n]];
		f[n]=d;
		return f[n];
	}
}
bool e(int x,int y)
{
	int p,q;
	p=find(x);
	q=find(y);
	if(p==q)
	  return 1;
	else
	{
		f[q]=p;
		o[q]+=c[p];
		c[p]+=c[q];
		return 0;
	}
}
main()
{
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	char k[100];
	int d,i,j;
	cin>>q;
	for(i=1;i<30001;i++)
	{
		f[i]=i;
		c[i]=1;
	}
	for(i=0;i!=q;i++)
	{
		t=getchar();
		while(t!='M'&&t!='C')
		  t=getchar();
		r(a);
		r(b);
		if(t=='M')
		  e(a,b);
		else
		  if(find(a)==find(b))
		  {
		  	d=abs(o[b]-o[a])-1;
		  	j=1;
		  	if(d<0)
		  	{
		  		cout<<'-';
		  		d=-d;
		  	}
		  	if(!d)
		  	  cout<<0;
		  	for(;d;d/=10,j++)
		  	  k[j]=d%10+'0';
		  	for(j--;j;j--)
		  	  cout<<k[j];
		  	cout<<endl;
		  }
		  else
		    cout<<-1<<endl;
	}
}