허용된 교환

도미니크는 양의 정수로 이루어진 배열 $p_1, \dots, p_N$을 생각했다. 이 배열을 오름차순으로 정렬한 결과를 $q_1, \dots, q_N$이라고 한다.

도미니크는 허용된 교환의 집합도 함께 생각했다. 쌍 $(X, Y)$가 허용된 교환의 집합에 들어 있으면, 도미니크는 배열 $p$의 위치 $X$와 위치 $Y$에 있는 수를 교환할 수 있다. 처음에 허용된 교환의 집합은 비어 있다.

마린은 도미니크에게 $Q$개의 질의를 준다. 각 질의는 다음 네 종류 중 하나다.

1. 위치 $A$와 위치 $B$의 수를 교환한다.

2. 쌍 $(A, B)$를 허용된 교환의 집합에 추가한다. 마린은 이미 집합에 들어 있는 쌍을 다시 줄 수도 있다.

3. 허용된 교환만 써서 배열을 정렬할 수 있는지 판정한다. 교환은 임의의 순서로 쓸 수 있고, 같은 교환을 몇 번이든 다시 써도 된다.

4. 위치 $A$에 있는 수를 허용된 교환만 써서 위치 $B$로 옮길 수 있으면 두 위치 $(A, B)$가 연결되어 있다고 한다. 위치 $A$와 연결된 모든 위치의 집합을 $A$의 구름이라고 한다. 어떤 구름에 속한 모든 위치 $j$에 대해 $p_j = q_j$가 동시에 성립하도록 허용된 교환을 적용할 수 있으면, 그 구름을 좋은 구름이라고 한다.

   다음 세 조건을 모두 만족하는 서로 다른 두 위치의 쌍 $(A, B)$가 몇 개인지 센다.

   • 위치 $A$와 위치 $B$는 연결되어 있지 않다.
   • $A$의 구름과 $B$의 구름이 모두 좋은 구름이 아니다.
   • 쌍 $(A, B)$를 허용된 교환의 집합에 추가하면, $A$의 구름과 $B$의 구름이 합쳐져서 생기는 $A$의 구름이 좋은 구름이 된다.

쌍 $(A, B)$와 $(B, A)$는 같은 쌍으로 센다.

첫째 줄에 정수 $N$과 $Q$가 주어진다 ($1 \le N, Q \le 10^6$).

둘째 줄에 $N$개의 정수 $p_1, \dots, p_N$이 주어진다 ($1 \le p_i \le 10^6$).

다음 $Q$개의 줄에 질의가 한 줄에 하나씩 주어진다.

• 줄의 첫 번째 수는 질의의 종류 $T$이고, 1, 2, 3, 4 중 하나다.
• $T$가 1 또는 2이면 그 뒤에 서로 다른 정수 $A$와 $B$가 온다 ($1 \le A, B \le N$).
• $T$가 3 또는 4이면 그 줄에는 다른 수가 없다.

종류가 3 또는 4인 질의마다 답을 한 줄에 출력한다.

종류 3의 답은 배열을 정렬할 수 있으면 DA, 정렬할 수 없으면 NE이다. 크로아티아어로 각각 예와 아니오를 뜻하며, 따옴표 없이 출력한다.

종류 4의 답은 문제에서 정의한, 음이 아닌 정수 하나다.

첫 번째 예제에서 $p = [1, 3, 2]$이고 $q = [1, 2, 3]$이다. 처음에는 허용된 교환이 하나도 없으므로 각 위치가 자기 자신만으로 이루어진 구름을 이룬다.

첫 번째 질의의 답은 1이다. 세 조건을 모두 만족하는 쌍은 $(2, 3)$ 하나뿐이다.

두 번째 질의의 답은 NE이다. 허용된 교환의 집합이 비어 있어서 2와 3을 제자리로 옮길 수 없다.

세 번째 질의로 쌍 $(2, 3)$이 허용된 교환의 집합에 들어간다.

네 번째 질의의 답은 0이다. 위치 2와 위치 3이 이미 연결되어 있다.

다섯 번째 질의의 답은 DA이다. 허용된 교환 $(2, 3)$을 한 번 적용하면 배열이 정렬된다.