COLOR.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int color[N], root_color[N];

struct DSU {
    int n; vector<int> root, hang;
    DSU(int n): n(n), root(n + 1), hang(n + 1) {
        for (int i = 1; i <= n; i++) {
            root[i] = i;
            hang[i] = 1;
        }
    }
    int find(int i) {
        if (i == root[i]) return i;
        return root[i] = find(root[i]);
    }
    bool join(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        if (hang[u] == hang[v]) hang[u]++;
        if (hang[u] < hang[v]) swap(u, v);
        root[v] = u;
        return true;
    }
};

void solve() {
    memset(color, 0, sizeof(color));
    memset(root_color, 0, sizeof(root_color));

    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    for (int i = 1; i <= n; i++) {
        int c; cin >> c;
        color[i] = c;
        if (!root_color[c]) {
            root_color[c] = i;
        }
        else {
            dsu.join(i, root_color[c]);
            root_color[c] = dsu.find(i);
        }
    }
    // color[dsu.find(i)] = mau cua vien i
    // root_color[c] = vien dai dien mau c
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            int i = root_color[x];
            if (i == 0) continue;
            root_color[x] = 0;
            if (!root_color[y]) {
                root_color[y] = i;
                color[i] = y;
            }
            else {
                dsu.join(i, root_color[y]);
                i = dsu.find(i);
                root_color[y] = i;
                color[i] = y;
            }
        }
        else {
            int i; cin >> i;
            cout << color[dsu.find(i)] << '\n';
        }
    }
}

int main() {
    int T; cin >> T;
    while (T--) solve();
}