\(\operatorname{p2b}[i]\coloneqq{}\)鳩 \(i\) が入っている箱の番号 として素直に処理を行うと、種類 \(2\) の操作で多くの鳩について更新を行う必要があるため、実行時間制限に間に合わせるのは難しいです。

ここで、仮想的な「ラベル鳩」を考え、次のように問題を読み替えます。

\(N\) 個の巣があり、はじめ \(i\) 番目の巣には鳩 \(i\) とラベル鳩 \(i\) が入っている。

次の操作を処理せよ。

1. 鳩 \(i\) を、ラベル鳩 \(j\) が入っている巣に移動させる。
2. ラベル鳩 \(i\) とラベル鳩 \(j\) を交換する。
3. 鳩 \(i\) と同じ巣に入っているラベル鳩の番号を出力する。

すると、各操作でたかだか \(2\) 羽の鳩についての情報を更新すればよいことになります。 種類 \(3\) の操作に正しく答えるために「 \(i\) 番目の巣に入っているラベル鳩の番号」を加えて管理する必要が生じますが、それを加えてもすべての操作を \(O(1)\) 時間で行うことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    using namespace std;
    
    unsigned N;
    cin >> N;

    // box_to_label : i 番目の巣に入っているラベル鳩の番号
    // label_to_box : i 番目のラベル鳩が入っている巣の番号
    // pigeon_to_box : i 番目の鳩が入っている巣の番号
    vector<unsigned> box_to_label(N), label_to_box(N), pigeon_to_box(N);
    iota(begin(box_to_label), end(box_to_label), 0U);
    iota(begin(label_to_box), end(label_to_box), 0U);
    iota(begin(pigeon_to_box), end(pigeon_to_box), 0U);

    unsigned Q;
    cin >> Q;
    for (unsigned q{}; q < Q; ++q) {
        unsigned type;
        cin >> type;
        if (type == 1) {
            unsigned pigeon, to;
            cin >> pigeon >> to;
            // 鳩 → 巣の情報を更新
            pigeon_to_box[pigeon - 1] = label_to_box[to - 1];
        } else if (type == 2) {
            unsigned label0, label1;
            cin >> label0 >> label1;
            // ラベル鳩 → 巣の情報を更新
            swap(label_to_box[label0 - 1], label_to_box[label1 - 1]);
            // 巣 → ラベル鳩の情報を更新
            swap(box_to_label[label_to_box[label0 - 1]], box_to_label[label_to_box[label1 - 1]]);
        } else {
            unsigned pigeon;
            cin >> pigeon;
            cout << box_to_label[pigeon_to_box[pigeon - 1]] + 1 << '\n';
        }
    }
    cout << flush;
    return 0;
}