Allowed swaps

Dominik has in mind an array of positive integers $p_1, \dots, p_N$. Write $q_1, \dots, q_N$ for the same array sorted in non-decreasing order.

He also has in mind a set of allowed swaps. If the pair $(X, Y)$ is in the set of allowed swaps, Dominik can swap the numbers at positions $X$ and $Y$ of the array $p$. The set of allowed swaps is empty at the start.

Marin gives Dominik $Q$ queries. Each query is one of the following four kinds.

1. Swap the numbers at positions $A$ and $B$.

2. Add the pair $(A, B)$ to the set of allowed swaps. Marin can give a pair that is already in the set.

3. Decide whether the array can be sorted using only the allowed swaps. The swaps can be used in any order, and each swap can be used any number of times.

4. Two positions $(A, B)$ are linked if the number at position $A$ can be moved to position $B$ using only allowed swaps. The set of all positions linked to position $A$ is the cloud of $A$. A cloud is good if the allowed swaps can be applied so that $p_j = q_j$ holds at the same time for every position $j$ of that cloud.

   Count the pairs of distinct positions $(A, B)$ that satisfy all three conditions below.

   • Positions $A$ and $B$ are not linked.
   • The cloud of $A$ is not good and the cloud of $B$ is not good.
   • Once the pair $(A, B)$ is added to the set of allowed swaps, the cloud of $A$ formed by joining the cloud of $A$ and the cloud of $B$ is good.

The pairs $(A, B)$ and $(B, A)$ count as the same pair.

The first line contains the integers $N$ and $Q$ ($1 \le N, Q \le 10^6$).

The second line contains $N$ integers $p_1, \dots, p_N$ ($1 \le p_i \le 10^6$).

Each of the next $Q$ lines contains one query.

• The first number on the line is the query kind $T$, one of 1, 2, 3, 4.
• If $T$ is 1 or 2, two different integers $A$ and $B$ follow ($1 \le A, B \le N$).
• If $T$ is 3 or 4, the line contains nothing else.

For each query of kind 3 or 4, print the answer on its own line.

The answer to a query of kind 3 is DA if the array can be sorted and NE if it cannot. These words are Croatian for yes and no, and they are printed without quotation marks.

The answer to a query of kind 4 is the non-negative integer defined in the statement.

In the first example $p = [1, 3, 2]$ and $q = [1, 2, 3]$. No swap is allowed at the start, so every position forms a cloud that holds only itself.

The answer to the first query is 1, because $(2, 3)$ is the only pair that satisfies all three conditions.

The answer to the second query is NE, because the set of allowed swaps is empty and the numbers 2 and 3 cannot reach their places.

The third query adds the pair $(2, 3)$ to the set of allowed swaps.

The answer to the fourth query is 0, because positions 2 and 3 are already linked.

The answer to the fifth query is DA, because one application of the allowed swap $(2, 3)$ sorts the array.