记得补启发式合并
算法一:并查集
/*
悲观看待成功,乐观看待失败。
author:leimingze
*/
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
const int N=1e6+10;
int f[N];
int n,q;
int ma[N],mb[N];//映射
int find(int x)
{
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
void unite(int a,int b)
{
int x=find(a),y=find(b);
if(x!=y)f[y]=x;
}
void solve()
{
cin>>n>>q;
int cnt_ball=n,cnt_box=n+q;
int maxv=n+2*q;
rep(i,1,maxv)f[i]=ma[i]=mb[i]=i;
while(q--)
{
int op,x,y;
cin>>op>>x;
if(op==1)
{
cin>>y;
unite(ma[x],ma[y]);
cnt_box++,ma[y]=cnt_box,mb[cnt_box]=y;
}
else if(op==2)unite(ma[x],++cnt_ball);
else cout<<mb[find(x)]<<endl;
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
}