For those who were struggling to understand D's solution (had an idea but couldnt convert it properly), i am writing this blog because it took me 2 hours to internalise it properly. I hope this helps someone and in case someone has a better intuition then please comment it.

Observation 1) Think of the nest numbers as labels, and think of where these nests are placed as indices. Initially index 1 has nest 1, index 2 has nest 2 and so on.....

Observation 2) When we are swapping birds of two nests A and B, we can look it at as : instead of swapping the birds, in nest A and B, we can swap the label of the nests itself.

We notice that once a bird has been placed on an index, we never really need to move the bird and only need to play with the labels.

Considering observation 2, since we are never going to move our birds, let us store the index at which we place the bird instead of label itself. For this we will need

1) birdToIndex[a] = x : denotes bird a is placed at INDEX x

2) indexToLabel[a] = x : denotes the nest label at index a is x (we need this because we later need to convert our index to label)

3) labelToIndex[a] = x : denotes that nest A is at index x, we need this because when we are told to place the bird at label a, we need to find the index associated with it.

So now it becomes straightforward :

If operation = 1 Then: bird[a] = labelToIndex[b] (stores index value of bird a)

If operation = 2 Then: we need to swap indices of nest a and b, as well as the labels of these indices need to be swapped

If operation = 3 Then : we need to out put indexToLabel[bird[a]]

Code :

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

int n, q;
std::vector<int> nestToIdx, lblToIdx, idxToLbl;
void solve(){
	cin >> n >> q;
	nestToIdx.resize(n+1);
	lblToIdx.resize(n+1);
	idxToLbl.resize(n+1);
	for(int i = 1; i <= n; i++){
		lblToIdx[i] = i;
		idxToLbl[i] = i;
		nestToIdx[i] = i;
	}
	for(int i = 0; i < q; i++){
		int type, a, b;
		cin >> type;
		if(type == 1){
			cin >> a >> b;
			nestToIdx[a] = b;
		}
		else if(type == 2){
			cin >> a >> b;
			int lb1 = a;
			int lb2 = b;
			int idx1 = lblToIdx[lb1];
			int idx2 = lblToIdx[lb2];
			idxToLbl[idx1] = b;
			idxToLbl[idx2] = a;
			swap(lblToIdx[lb1], lblToIdx[lb2]);
		}
		else{
			cin >> a;
			cout<< idxToLbl[nestToIdx[a]] << "\n";
		}
	}
}
 
int main(){
	int t = 1;
	//cin >> t;
	
	while(t--){
		solve();
	}
 
	return 0;
}