Description

Dominik builds an array $p_1,p_2,\dots,p_n$ with $n$ elements, and the array $q_1,q_2,\dots,q_n$ obtained by sorting it.

He also defines a “swappable set”. If an unordered pair $(a,b)$ belongs to the “swappable set”, then he can swap the positions of $p_a$ and $p_b$. “Using the swappable set” means performing a number of such swaps.

There are four operations:

• Operation $1$:

  Format: 1 a b.

  Swap $p_a$ and $p_b$ (not restricted by the “swappable set”).

• Operation $2$:

  Format: 2 a b.

  Add the unordered pair $(a,b)$ to the “swappable set”.

• Operation $3$:

  Format: 3.

  Determine whether the array $p$ can be sorted using the “swappable set”.

• Operation $4$:

  Format: 4.

  If the $x$-th element in array $p$ can be moved to position $y$ using the “swappable set”, then $x$ and $y$ are said to be connected. Here $x$ may be equal to $y$.

  The set of all $y$ connected to $x$ is called the “cloud” of $x$. If a “cloud” can use the “swappable set” to make every $i$ in the “cloud” satisfy $p_i=q_i$, then this “cloud” is called an “auspicious cloud”.

  Compute how many unordered pairs $(a,b)$ satisfy:

  • $1\le a,b\le n$ and $a\not=b$.
  • $a$ and $b$ are not connected.
  • Neither the “cloud” of $a$ nor the “cloud” of $b$ is an “auspicious cloud”.
  • After adding the unordered pair $(a,b)$ to the “swappable set”, the “cloud” of $a$ becomes an “auspicious cloud”.

Please help Dominik complete these operations.

Input Format

The first line contains two integers $n,q$, representing the number of elements in array $p$ and the number of operations.

The second line contains $n$ integers $p_i$.

The next $q$ lines are given in the following format:

1. An integer $t$, representing the type of the operation.

2. If $t$ is $1$ or $2$, then two distinct integers $a,b$ follow.

Output Format

• For each operation $3$:

  If the array $p$ can be sorted using the “swappable set”, output one line DA.

  Otherwise, output one line NE.

• For each operation $4$:

  Output one line with an integer, representing the number of unordered pairs $(a,b)$ that satisfy the conditions.

3 5
1 3 2
4
3
2 2 3
4
3 

1
NE
0
DA 

5 5
4 2 1 4 4
3
4
1 1 3
3
4 

NE
1
DA
0 

4 10
2 1 4 3
3
4
1 1 2
3
4
2 2 3
2 1 2
4
2 3 4
3 

NE
2
NE
1
3
DA 

Hint

Sample 1 Explanation

• The first operation: only the unordered pair $(2,3)$ satisfies the requirement.
• The second operation: the array $p$ cannot be sorted using the “swappable set”.
• The third operation: add the unordered pair $(2,3)$ to the “swappable set”.
• The fourth operation: there is no unordered pair that satisfies the requirement.
• The fifth operation: swap $p_2$ and $p_3$, and then the array $p$ can be sorted using the “swappable set”.

Constraints

For $100\%$ of the data, $1\le n,q\le 10^6$, $1\le p_i\le 10^6$, $1\le t\le 4$, $1\le a,b\le n$ and $a\not=b$.

Notes

This problem is translated from COCI2016-2017 CONTEST #2 T5 Zamjene.

Translated by ChatGPT 5