Problem Description

Dominik has constructed an array \( p \) with \( n \) elements, \( p_1, p_2, \dots, p_n \), and its sorted version \( q_1, q_2, \dots, q_n \).

He also defines the "exchangeable set". If the unordered pair \( (a, b) \) belongs to the "exchangeable set", he can swap the positions of \( p_a \) and \( p_b \). "Through the 'exchangeable set'" means through several such swaps.

There are four types of operations:

• Operation 1:
• Format: 1 a b.

• Swap the positions of \( p_a \) and \( p_b \) (not restricted by the "exchangeable set").

• Operation 2:

• Format: 2 a b.

• Add the unordered pair \( (a, b) \) to the "exchangeable set".

• Operation 3:

• Format: 3.

• Determine if it is possible to sort array \( p \) through the "exchangeable set".

• Operation 4:

• Format: 4.
• If the \( x \)-th element in array \( p \) can be moved to the \( y \)-th position through the "exchangeable set", then \( x \) and \( y \) are connected. Here, \( x \) may equal \( y \).
• The set of all \( y \) connected to \( x \) is called \( x \)'s "cloud". If a "cloud" can be arranged through the "exchangeable set" such that any \( i \) in the "cloud" satisfies \( p_i = q_i \), then this "cloud" is a "lucky cloud".
• Calculate the number of unordered pairs \( (a, b) \) that satisfy:
  • \( 1 \le a, b \le n \) and \( a \neq b \).
  • \( a \) and \( b \) are not connected.
  • Neither \( a \)'s "cloud" nor \( b \)'s "cloud" is a "lucky cloud".
  • Adding the unordered pair \( (a, b) \) to the "exchangeable set" makes \( a \)'s "cloud" a "lucky cloud".

Please help Dominik complete these operations.

Input Format

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

The second line contains \( n \) integers \( p_i \).

The next \( q \) lines are given in the following format:

1. An integer \( t \), indicating the type of operation.
2. If \( t \) is 1 or 2, two distinct integers \( a \) and \( b \) are provided.

Output Format

• For each operation 3:
• If it is possible to sort array \( p \) through the "exchangeable set", output one line DA.

• Otherwise, output one line NE.

• For each operation 4:

• Output one line containing an integer, representing the number of unordered pairs \( (a, b) \) that meet the conditions.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
NE
0
DA

Input Sample #2

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

Output Sample #2

NE
1
DA
0

Input Sample #3

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

Output Sample #3

NE
2
NE
1
3
DA

Notes/Hints

Sample 1 Explanation

• First operation: Only the unordered pair \( (2, 3) \) meets the requirements.
• Second operation: It is not possible to sort array \( p \) through the "exchangeable set".
• Third operation: Add the unordered pair \( (2, 3) \) to the "exchangeable set".
• Fourth operation: No unordered pairs meet the requirements.
• Fifth operation: Swapping \( p_2 \) and \( p_3 \) allows sorting array \( p \) through the "exchangeable set".

Data Size and 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 \neq b \).

Notes

Translated from COCI2016-2017 CONTEST #2 T5 Zamjene.

见题面 Input 部分

见题面 Output 部分