首先建出操作树，设当前是第 $i$ 次操作。

• 若 $1,3$ 操作，$i-1 \to i$。
• 否则 $x \to i$。

然后在操作树上 dfs，再考虑处理连通块第 $k$ 小的问题。
首先连通块容易想到用冰茶寄维护，由于要回溯所以可撤销冰茶寄。
其次第 $k$ 小这个东西很难直接用 log 数据结构维护，所以考虑对值域分块。
具体地，设 $cnt_{i,j}$ 表示 $i$ 为根的连通块，点权在 $j$ 这一段的点的数量。

合并是简单的，按秩合并。
撤销也是简单的，注意补药搞错 $x,y$ 的编号。

查询 $x$ 所属连通块的第 $k$ 小？
先大段往后跳，然后小段内遍历即可。

其实代码也不难，就是细节容易趋势。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = N, B = 2173, C = 1e5 / B + 1;
int n, m;
struct node { int x, id; } a[N];
inline bool cmp(node a, node b) { return a.x < b.x; }

int h[N], e[M], ne[M], idx = 0;
inline void add(int a, int b) { /*cout << a << ' ' << b << endl;*/ e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

int p[N], sz[N];
inline int find(int x) { return (p[x] == x) ? x : find(p[x]); }

short cnt[N][C], len = 0;
inline void init() {
    len = (n - 1) / B + 1;
    for (register int i = 1; i <= n; i++) {
        p[i] = i, sz[i] = 1;
        cnt[a[i].id][(i - 1) / B + 1] = 1;
    }
}

int opt[N], x[N], y[N];
int ans[N];

inline void dfs(int u) {
    // cout << '\t' << u << endl;
    bool merge = 0;
    int dn = 0, up = 0;
    if (opt[u] == 1) {
        int A = find(x[u]), B = find(y[u]);
        if (A != B) {
            if (sz[A] > sz[B]) swap(A, B), swap(x[u], y[u]);    //A under B
            dn = A, up = B, merge = 1;
            for (register int i = 1; i <= len; i++) cnt[up][i] += cnt[dn][i];
            p[dn] = up, sz[up] += sz[dn];
        }
    }
    if (opt[u] == 3) {
        int A = find(x[u]), k = y[u]; //A 连通块第 k 大
        // cout << '\t' << A << ' ' << k << ' ' << sz[A] << endl;
        if (k <= 0 || k > sz[A]) ans[u] = -1;
        else {
            int id = 1;
            while (k > cnt[A][id]) k -= cnt[A][id], id++;
            for (register int i = (id - 1) * B + 1; i <= min(id * B, n); i++) {
                if (find(a[i].id) == A) k--;
                if (k == 0) { ans[u] = a[i].x; break; }
            }
        }
    }
    for (register int i = h[u]; ~i; i = ne[i]) dfs(e[i]);
    //------------------------
    if (merge) {
        for (register int i = 1; i <= len; i++) cnt[up][i] -= cnt[dn][i];
        p[dn] = dn, sz[up] -= sz[dn];
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++) scanf("%d", &a[i].x), a[i].id = i;
    sort(a + 1, a + 1 + n, cmp);
    init();
    // for (register int i = 1; i <= n; i++) cout << a[i].x << ' '; puts("");
    for (register int i = 1; i <= m; i++) {
        scanf("%d", &opt[i]);
        if (opt[i] == 1) {
            add(i - 1, i);
            scanf("%d%d", &x[i], &y[i]);
        } else if (opt[i] == 2) {
            int pre; scanf("%d", &pre);
            add(pre, i);
        } else {
            add(i - 1, i);
            scanf("%d%d", &x[i], &y[i]);
        }
    }
    dfs(0);
    for (register int i = 1; i <= m; i++)
        if (opt[i] == 3) printf("%d\n", ans[i]);
    return 0;
}