An operation of type \(1\) is merging sets, so it can be directly handled with the Disjoint Set Union (DSU). Thus, we want to exploit DSU to solve this problem.

First of all, we only have to consider the balls numbered up to \(N+Q\). Also, since an operation of type \(1\) is merging sets of balls, it seems that it is sufficient to prepare a DSU with \(N+Q\) elements to handle the addition of balls.

The problem is those of type \(3\): “the set of many balls” may wander rapidly. (For example, the queries may ask you to put about \(10^5\) balls into box \(1\), and then move them to boxes \(2,3,\dots\), and so on.) Thus, we cannot update the box that each ball belongs; otherwise it leads to TLE (Time Limit Exceeded).
Instead, we may maintain the box that each “set of balls” belongs. If we can move a set instead of balls, we would reduce the complexity.
Let us implement this solution.

The key is the function in DSU that returns the representative element, as in “leader” function in dsu in ACL (AtCoder Library).

Let us maintain the following pieces of information:

• \(ld[x] = \) the representative element of the set of balls contained in box \(x\), or \(-1\) if it is empty;
• \(ing[y] = \) the box that the set represented by \(y\) belongs to, or an indeterminate value if there is no set represented by \(y\).

Type \(1\):

• If box \(Y\) is empty, do nothing.
• Otherwise, if box \(X\) is empty, move the contents of box \(Y\) to box \(X\) as follows:
  • Let \(ld[X]=ld[Y]\), which corresponds to moving the set contained in box \(Y\) to box \(X\).
  • Let \(inv[ld[X]]=X\).
  • Let \(ld[Y]=-1\), emptying box \(Y\).
• Otherwise, both box \(X\) and \(Y\) contain one or more balls, so do the following steps:
  • Merge the set represented by \(ld[X]\) with the one represented by \(ld[Y]\). Let \(ld[X]\) be the new representative element of that set.
  • Let \(inv[ld[X]]=X\).
  • Let \(ld[Y]=-1\).

Type \(2\):
Let \(b\) the index of the new ball.

• If box \(X\) is empty, let \(ld[X]=b\) and \(inv[ld[X]]=X\).
• Otherwise, merge the set of balls represented by \(ld[X]\) with the one by \(b\), and let \(b\) the representative element of the set. Then let \(inv[ld[X]]=X\).

Type \(3\):
Print \(inv[tg]\), where \(tg\) is the representative element that contains ball \(X\).

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder;

int main(){
  int n,q;
  cin >> n >> q;
 
  dsu uf(n+q+5);
  int balls=n;
 
  vector<int> ld(n+1,-1);
  vector<int> inv(n+q+5);
  for(int i=1;i<=n;i++){
    ld[i]=i;
    inv[ld[i]]=i;
  }
 
  for(int tr=0;tr<q;tr++){
    int typ;
    cin >> typ;
    if(typ==1){
      int x,y;
      cin >> x >> y;
      if(ld[y]==-1){continue;}
      else if(ld[x]==-1){
        ld[x]=ld[y];
        inv[ld[x]]=x;
        ld[y]=-1;
      }
      else{
        uf.merge(ld[x],ld[y]);
        ld[x]=uf.leader(ld[x]);
        inv[ld[x]]=x;
        ld[y]=-1;
      }
    }
    if(typ==2){
      int x;
      cin >> x;
      balls++;
      if(ld[x]==-1){
        ld[x]=balls;
        inv[ld[x]]=x;
      }
      else{
        uf.merge(ld[x],balls);
        ld[x]=uf.leader(balls);
        inv[ld[x]]=x;
      }
    }
    if(typ==3){
      int x;
      cin >> x;
      int tg=uf.leader(x);
      cout << inv[tg] << "\n";
    }
  }
  return 0;
}