題目描述

公元五八○一年，地球居民遷移至金牛座α第二行星，在那里發(fā)表銀河聯(lián)邦

創(chuàng)立宣言，同年改元為宇宙歷元年，并開始向銀河系深處拓展。

宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭。泰山壓

頂集團(tuán)派宇宙艦隊(duì)司令萊因哈特率領(lǐng)十萬余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊

威利組織麾下三萬艘戰(zhàn)艦迎敵。

楊威利擅長排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在

這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場劃分成30000列，每列依次編號為1, 2, …,

30000。之后，他把自己的戰(zhàn)艦也依次編號為1, 2, …, 30000，讓第i號戰(zhàn)艦處于

第i列(i = 1, 2, …, 30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當(dāng)

進(jìn)犯之?dāng)车竭_(dá)時(shí)，楊威利會多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，

實(shí)施密集攻擊。合并指令為M i j，含義為讓第i號戰(zhàn)艦所在的整個(gè)戰(zhàn)艦隊(duì)列，作

為一個(gè)整體（頭在前尾在后）接至第j號戰(zhàn)艦所在的戰(zhàn)艦隊(duì)列的尾部。顯然戰(zhàn)艦

隊(duì)列是由處于同一列的一個(gè)或多個(gè)戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會使隊(duì)列增

大。 然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通

過龐大的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽楊威利的艦隊(duì)調(diào)動(dòng)指令。

在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)

艦分布情況，也會發(fā)出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利

的第i號戰(zhàn)艦與第j號戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之

間布置有多少戰(zhàn)艦。

作為一個(gè)資深的高級程序設(shè)計(jì)員，你被要求編寫程序分析楊威利的指令，以

及回答萊因哈特的詢問。

最終的決戰(zhàn)已經(jīng)展開，銀河的歷史又翻過了一頁……

輸入輸出格式

輸入格式： 輸入文件galaxy.in的第一行有一個(gè)整數(shù)T（1<=T<=500,000），表示總共有T

條指令。

以下有T行，每行有一條指令。指令有兩種格式：

M i j ：i和j是兩個(gè)整數(shù)（1<=i , j<=30000），表示指令涉及的戰(zhàn)艦編號。 該指令是萊因哈特竊聽到的楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，并且保證第i號戰(zhàn)

艦與第j號戰(zhàn)艦不在同一列。

C i j ：i和j是兩個(gè)整數(shù)（1<=i , j<=30000），表示指令涉及的戰(zhàn)艦編號。 該指令是萊因哈特發(fā)布的詢問指令。

輸出格式： 輸出文件為galaxy.out。你的程序應(yīng)當(dāng)依次對輸入的每一條指令進(jìn)行分析和

處理：

如果是楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，則表示艦隊(duì)排列發(fā)生了變化，你的程序

要注意到這一點(diǎn)，但是不要輸出任何信息；

如果是萊因哈特發(fā)布的詢問指令，你的程序要輸出一行，僅包含一個(gè)整數(shù)，

表示在同一列上，第i 號戰(zhàn)艦與第j 號戰(zhàn)艦之間布置的戰(zhàn)艦數(shù)目。如果第i 號戰(zhàn)

艦與第j號戰(zhàn)艦當(dāng)前不在同一列上，則輸出-1。

輸入輸出樣例

輸入樣例#1： 4 M 2 3 C 1 2 M 2 4 C 4 2 輸出樣例#1： -1 1 說明

【樣例說明】

戰(zhàn)艦位置圖：表格中阿拉伯?dāng)?shù)字表示戰(zhàn)艦編號

分析： 這是去年在紀(jì)中做過的例題，就不解釋了

代碼：

include

include

include

include

using namespace std; const int maxn=30000+10;

int p[maxn],value[maxn],num[maxn]; int findset(int x,int &pson) { if(p[x]==x) { pson=x;return 0; } else { value[x]+=findset(p[x],p[x]); pson=p[x]; return value[x]; } }

void change(int x,int y) { int a ,b; findset(x,fx); findset(y,fy); p[fx]=fy; value[fx]=num[fy]; num[fy]+=num[fx]; num[fx]=0; }

void ask(int x,int y) { int fx,fy; findset(x,fx); findset(y,fy); if(fx!=fy)PRintf(“-1/n”); else printf(“%d/n”,abs(value[x]-value[y])-1); return ; }

int main() { int T;cin>>T; char ins[10]; int x,y; for(int i=1;i<=maxn-10;i++) p[i]=i,num[i]=1; while(T–) { scanf(“%s%d%d”,ins,&x,&y); if(ins[0]==’M’) change(x,y); else ask(x,y); } return 0; }