、思路：首先是并查集来做，首先给给每个单词一个id，然后把它放到ans[i]处。

对于操作1：把a单词换为单词b，就相当于a、b两个集合结合。然后再给a单词赋一个新的id，用来进行操作2，因为之后的操作2可能会出现a这个单词，并且没有转化为b单词，就需要一个新的id。

对于操作2：就是改变一下答案中目标位置的单词即可。

-----------------------------------

逆序的话，就是倒着从最晚操作的来改变文章

操作1：就是简单的把单词a改为单词b。

操作2：因为当前操作排在后面，当前面无论做什么改变当前位置单词也不会改变。

代码：

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;
const int N = 100010;


int n, q;
vector<string>ans(N);
map<string,int>mp;
int p[N];

int find(int x){
    if(x != p[x])
        p[x] = find(p[x]);
    return p[x];
}

void solve(){
    cin >> n >> q;
    vector<int>novel(n);

    int num = 0;

    auto getid = [&] (const string &s, bool override = false){
        if(!mp.count(s) || override){
            ans[num] = s;
            mp[s] = num ++;
        }
        return mp[s];
    };

    for(int i = 1;i <= n + q * 2;i ++)
        p[i] = i;

    for(int i = 0;i < n;i ++){
        string s;
        cin >> s;
        novel[i] = getid(s);
    }

    while(q --){
        int op;
        cin >> op;
        if(op == 1){
            string x, y;
            cin >> x >> y;
            if(x == y || !mp.count(x))
                continue;
            p[find(getid(x))] = find(getid(y));
            getid(x, true);
        }else{
            string y;
            int k;
            cin >> k;
            cin >> y;
            novel[k - 1] = getid(y);
        }
    }
    for(int i = 0;i < n;i ++){
        cout << ans[find(novel[i])] << ' ';
    }
}

void task(int TestCase) {
    int n, q;
    cin >> n >> q;
    vector<string> s(n);
    map<string, string> mp;
    for (auto &x : s) {
        cin >> x;
        mp[x] = x;
    }

    vector<array<string, 3>> opt;
    for (int i = 0; i < q; i++) {
        string x, y, z;
        cin >> x >> y >> z;
        opt.push_back({x, y, z});
        mp[z] = z;
    }

    vector<int> vis(n);
    for (int i = q - 1; i >= 0; i--) {
        auto &[x, y, z] = opt[i];
        if (x == "1") {
            mp[y] = mp[z];
        } else {
            int pos = stoi(y) - 1;
            if (!vis[pos]) {
                s[pos] = mp[z];
                vis[pos] = 1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << (vis[i] ? s[i] : mp[s[i]]) << " \n"[i + 1 == n];
    }
}
signed main()
{
//     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // int t = 1;
    // while(t--)
    // {
    //     solve();
    // }
    task(1);
    return 0;
}