# 某岛

… : "…アッカリ～ン . .. . " .. .
March 20, 2020

## Vijos 1443. 银河英雄传

Vijos 传送门

```namespace DSU{ // Disjoint Set Union
const int N = int(3e4) + 9;
int P[N], R[N], prv[N], cnt[N], n;
inline void Make(int x){
P[x] = x, R[x] = 0;
prv[x] = 0; cnt[x] = 1;
}
inline int Find(int x){
if (P[x] == x){
return x;
}
else{
int t = Find(P[x]);
prv[x] += prv[P[x]];
P[x] = t;
return P[x];
}
//return P[x] == x ? x : P[x] = Find(P[x]);
}
inline void Unionn(int x, int y){
//if (R[x] == R[y]) ++R[x];
//else if (R[x] < R[y]) swap(x, y);

P[y] = x;
prv[y] += cnt[x];
cnt[x] += cnt[y];
}
inline void Union(int x, int y){
x = Find(x), y = Find(y), Unionn(x, y);
}
inline void Init(){
REP_1(i, n) Make(i);
}
} using namespace DSU;

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

n = int(3e4); Init();

Rush{
char cmd; RC(cmd); int x, y; RD(x, y); if (cmd == 'M'){
//cout << x << " " << y << endl;
Union(y, x);
}
else{
//cout << Find(x) << " " << Find(y) << endl;
if (Find(x) != Find(y)) puts("-1");
else{
printf("%d\n", abs(prv[x] - prv[y]) - 1);
}
}
}
}
```