#include <iostream>
#include <random>
#include <chrono>
#include <map>
#include <algorithm>
using namespace std;
#define int long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1<<20, M1 = 998244353, M2 = 1000000013999999951;
int num[N], slot[N], cnt, gd, Par[N], rts, vl[N], p[N], q[N], sz[N];
map<int, int> mp;
int root(int v){
return (Par[v] == 0 ? v : Par[v] = root(Par[v]));
}
int get(int A, int B){
while (B < 0)
B += M2;
A += B;
while (A >= M2)
A -= M2;
return A;
}
void eraseData(int i){
if (slot[i] == num[i])
gd--;
else{
cnt -= mp[get(num[i], -slot[i])] * sz[root(i)];
mp[get(slot[i], -num[i])] -= sz[root(i)];
}
}
void insertData(int i){
if (slot[i] == num[i])
gd++;
else{
cnt += mp[get(num[i], -slot[i])] * sz[root(i)];
mp[get(slot[i], -num[i])] += sz[root(i)];
}
}
void Add(int &A, int B){
while (B < 0)
B += M2;
// cout<<A<<"\n"<<B<<"\n";
A += B;
// cout<<A<<endl<<endl;
while (A >= M2)
A -= M2;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m;
cin>>n>>m, rts = n;
vl[0] = rng();
for (int i=1;i<N;i++){
// vl[i] = (i == 1 ? 1 : vl[i-1] * 2 % M1);
vl[i] = vl[i-1] % M1 * rng() % M2;
}
for (int i=1;i<=n;i++)
cin>>p[i], q[i] = p[i], sz[i] = 1;
sort(q + 1, q + n + 1);
for (int i=1;i<=n;i++){
slot[i] = vl[q[i]];
num[i] = vl[p[i]];
// cout<<i<<" "<<p[i]<<" "<<q[i]<<" "<<vl[p[i]]<<" "<<vl[q[i]]<<endl;
insertData(i);
}
while (m--){
// for (int i=1;i<=n;i++){
// if (i == root(i))
// cout<<i<<" "<<slot[i]<<" "<<num[i]<<endl;
// }
// cout<<"finally, "<<gd<<" "<<cnt<<endl;
// cout<<endl<<endl<<endl;
int t, A, B;
cin>>t;
if (t == 1){
cin>>A>>B;
int a = root(A), b = root(B);
if (a == b)
swap(p[A], p[B]);
else{
eraseData(a);
eraseData(b);
Add(num[a], get(vl[p[B]], -vl[p[A]]));
Add(num[b], get(vl[p[A]], -vl[p[B]]));
swap(p[A], p[B]);
insertData(a);
insertData(b);
// cout<<slot[a]<<" "<<num[a]<<" "<<slot[b]<<" "<<num[b]<<endl;
}
}
else if (t == 2){
cin>>A>>B;
int a = root(A), b = root(B);
if (a == b)
continue;
eraseData(a);
eraseData(b);
Add(num[a], num[b]);
Add(slot[a], slot[b]);
Par[b] = a;
sz[a] += sz[b];
insertData(a);
rts--;
}
else if (t == 3){
// cout<<gd<<" "<<rts<<' ';
if (gd == rts)
cout<<"DA\n";
else
cout<<"NE\n";
}
else{
cout<<cnt<<'\n';
}
}
}
