Balls と boxes の対応を表す写像を作りたい． ただし，balls は同じ箱に入っているものは同一視できるから， 類別して代表系で考える． つまり union-find が便利． $$f : Balls / \sim \ \rightarrow \ Boxes,$$ $$g : Boxes \ \rightarrow \ Balls / \sim $$ を作る．
実装: まずは box 同士を結合する操作や， まだ入ってないボールを箱に入れる操作を実装する． その後，空のbox などの例外処理を書けばよい． 先に骨組みを書いてから例外を書くと簡単．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, q;
cin >> n >> q;
ll N = n + q + 10;
UnionFind<ll> uf(N);
map<ll,ll> f, g;
rep(i,n){
f[i] = i;
g[i] = i;
}
k = n;
rep(qi,q){
ll x,y,op;
cin >> op >> x;
--x;
if(op == 1){
// x,y : box
cin >> y;
--y;
if(g[y] == -1) continue;
if(g[x] == -1){
g[x] = g[y];
f[g[x]] = x;
}else{
uf.merge(g[x],g[y]);
}
// f[g[y]] = f[g[x]]; // 有っても無くても AC
g[y] = -1;
assert(f[g[x]] == x);
}else if(op == 2){
// x : box
if(g[x] == -1){
f[k] = x;
g[x] = k;
}else{
uf.merge(g[x],k);
}
k++;
}else{
// x : ball
// cout << "-----";
cout << f[uf[x]]+1 << endl;
}
}
return 0;
}
