题目描述

Dominik 构造了一个含有 $n$ 个元素的数组 $p_1,p_2,\dots,p_n$，和对其排序得到的数组 $q_1,q_2,\dots,q_n$。

此外，他还定义了「可交换集」。若无序数对 $(a,b)$ 属于「可交换集」，则他可以交换 $p_a,p_b$ 的位置。『通过「可交换集」』，即为通过若干次这样的交换。

现有四种操作：

• 操作 $1$：

  格式：1 a b。

  交换 $p_a,p_b$ 的位置（不受「可交换集」限制）。

• 操作 $2$：

  格式：2 a b。

  将无序数对 $(a,b)$ 加入「可交换集」。

• 操作 $3$：

  格式：3。

  判断能否通过「可交换集」完成对数组 $p$ 的排序。

• 操作 $4$：

  格式：4。

  若数组 $p$ 中的第 $x$ 个元素能通过「可交换集」移至第 $y$ 位，则称 $x,y$ 是相连的。其中 $x$ 可能等于 $y$。

  将所有与 $x$ 相连的 $y$ 构成的集合称作 $x$ 的「云」。若一朵「云」能通过「可交换集」使得「云」中任意的 $i$ 满足 $p_i=q_i$，则称这朵「云」是「祥云」。

  计算有多少组无序数对 $(a,b)$ 满足：

  • $1\le a,b\le n$ 且 $a\not=b$。
  • $a,b$ 不是相连的。
  • $a$ 的「云」与 $b$ 的「云」均不是「祥云」。
  • 将无序数对 $(a,b)$ 加入「可交换集」后，$a$ 的「云」变为「祥云」。

请你帮助 Dominik 完成这些操作。

输入格式

第一行两个整数 $n,q$，表示数组 $p$ 中元素的个数和操作次数。

第二行 $n$ 个整数 $p_i$。

接下来 $q$ 行按以下格式给出：

1. 一个整数 $t$，表示操作的类型。

2. 若 $t$ 为 $1$ 或 $2$，接下来给出两个不同的整数 $a,b$。

输出格式

• 对于每一次操作 $3$：

  若能通过「可交换集」完成对数组 $p$ 的排序，输出一行 DA。

  否则，输出一行 NE。

• 对于每一次操作 $4$：

  输出一行，一个整数，表示满足条件的无序数对 $(a,b)$ 组数。

样例 #1

样例输入 #1

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

样例输出 #1

1
NE
0
DA

样例 #2

样例输入 #2

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

样例输出 #2

NE
1
DA
0

样例 #3

样例输入 #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

样例输出 #3

NE
2
NE
1
3
DA

提示

样例 1 解释

• 第一次操作：仅有无序数对 $(2,3)$ 满足要求。
• 第二次操作：不能通过「可交换集」完成对数组 $p$ 的排序。
• 第三次操作：将无序数对 $(2,3)$ 加入「可交换集」。
• 第四次操作：不存在满足要求的无序数对。
• 第五次操作：交换 $p_2,p_3$，即可通过「可交换集」完成对数组 $p$ 的排序。

数据规模与约定

对于 $100\%$ 的数据，$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$ 且 $a\not=b$。