<h1>题意描述</h1>

有 300,000 个元素，每种元素初始时以单独队列存在，支持下面两种操作：

1.合并两个队列，即将x元素所在队列首部接至y元素所在队列的尾部。
2.查询两个元素x,y是否在同一队列，如果是，则求两元素的间隔元素的数量

操作 500,000 次

<h1>链接</h1>

洛谷

<h1>题解</h1>

我们可以显而易见看出这是一道并查集的题目，在这里我们要使用一种叫做带权并查集的东西。
对于带权并查集，我们需要维护一个权值$ dist[i] $表示$ i $到$ f[i] $的距离。
然后就套用并查集模版，注意路径压缩和合并时候顺便处理一下$ dist[i] $即可。

<h1>代码</h1>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

const int MAXN = 30000 + 5;

inline void Read(int &x){  //快读提高速度
    int ret = 0,flag = 1;
    x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0'){
        if(ch == '-') flag = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        ret = (ret << 1) + (ret << 3) + ch - '0';
        ch = getchar();
    }
    x = ret * flag;
}

int f[MAXN],num[MAXN],dist[MAXN],t;
//f[i]表示i的父亲，num[i]表示i所在队列的大小，dist[i]表示i到f[i]的距离。

inline void init(){   //初始化并查集
    for(int i = 1;i <= MAXN;i++){
        f[i] = i;
        num[i] = 1;
    }
}

int find(int x){  //查找+路径压缩
    if(x != f[x]){
        int t = f[x];
        f[x] = find(f[x]);
        dist[x] += dist[t];
        num[x] = num[f[x]];
    }
    return f[x];
}

void Union(int x,int y){  //合并x,y所在的队列
    int fx = find(x), fy = find(y);
    if(fx != fy){
        f[fx] = fy;
        dist[fx] = dist[fy] + num[fy];
        num[fy] += num[fx];
        num[fx] = num[fy];
    }
}

int query(int a,int b){  //查询x,y的距离
    int fa = find(a),fb = find(b);
    if(fa != fb) return -1;
    else
        return std::abs(dist[a] - dist[b]) - 1;
}

inline bool istrue(char ch){  //特判读入
    return ch == 'C' || ch == 'M';
}

int main(){
    int T;
    Read(T);
    init();
    for(int i = 1;i <= T;i++){
        char ch;
        while(!istrue(ch = getchar())); //这里读入有坑，我WA了3次才知道
        //scanf("%c",&ch);   //错误的做法
        int l,r;
        Read(l);Read(r);
        if(ch == 'M') Union(l,r);
        else printf("%dn",query(l,r));
    }
    //getchar();getchar();
    return 0;
}