If you try to naively maintain information like \(\operatorname{p2b}[i]\coloneqq{}\) (the index of the box pigeon \(i\) is currently in), the operation of the second kind requires performing operations for many pigeons, so it is difficult to finish within the time limit.

Instead, let us consider virtual “label pigeons” to reinterpret the problem as follows:

There are \(N\) nests. Initially, nest \(i\) has pigeon \(i\) and label pigeon \(i\).

Process the following operations.

1. Move pigeon \(i\) to the nest where label pigeon \(j\) is currently in.
2. Swap label pigeon \(i\) and label pigeon \(j\).
3. Print the label of the label pigeon that is in the same nest as pigeon \(i\).

Then, each operation requires moving at most two pigeons. To answer type-\(3\) queries properly, we need to maintain additional information like “the index of label pigeon that is currently in nest \(i\).” Nevertheless, all the operations can be performed in \(O(1)\) time.

The following is sample code.

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

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

    // box_to_label : the index of the label pigeon that is in nest i
    // label_to_box : the index of the nest that label pigeon i is in
    // pigeon_to_box : the index of the nest that pigeon i is in
    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;
            // Update pigeon-to-nest mapping
            pigeon_to_box[pigeon - 1] = label_to_box[to - 1];
        } else if (type == 2) {
            unsigned label0, label1;
            cin >> label0 >> label1;
            // Update label-pigeon-to-nest mapping
            swap(label_to_box[label0 - 1], label_to_box[label1 - 1]);
            // Update nest-to-label-pigeon mapping
            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;
}