编程题：模拟+哈希表优化
$$Dominik$$设想了一个正整数数组$$p1，…，pn$$。我们把排序后的数组表示为$$q1，…，qn$$。
此外，他设想了一套允许的替换。如果一对$$(X, Y)$$是允许替换集合的成员，$$Dominik$$可以交换数组$$p$$中$$X$$和$$Y$$位置的数字。
$$Marin$$给$$Dominik Q$$查询，每个都是以下类型之一:
1. 交换位置$$A$$和$$B$$的数字。
2. 将对$$(A, B)$$添加到允许替换的集合中。$$Marin$$可以给出一对$$(A, B)$$它已经在允许替换的集合中了。
3.看看是否有可能只使用允许的替换对数组进行排序?替换可以以任意顺序使用，并且每个替换可以进行任意次数。
4.如果仅使用允许的替换就可以将位置$$a$$的数字转移到位置$$B$$，那么我们将这对位置$$(a, B)$$连接起来。我们称与位置$$A$$相关的所有位置的集合为$$A$$的云。如果从云中的每个位置$$j$$都有可能使用一系列允许的替换来实现$$p_{j} = q_{j}$$，那么云就是好的。
你必须回答有多少对不同的位置$$(A, B)$$存在，使其成立：
a.位置$$a$$和位置$$B$$没有链接
b. $$A$$云不好，$$B$$云也不好
c.如果我们在允许替换的集合中加入一对$$(A, B)$$， $$A$$的云(通过连接$$A$$的云和$$B$$的云)就会变得很好。
请注意：配对$$(A, B)$$和$$(B, A)$$被认为是相同的一对。
### 输入格式:
第一行输入包含整数$$N$$和$$Q(1≤N, Q≤1 000 000)$$。
输入的第二行包含$$N$$个整数$$p1，…，pn(1≤p1，…，pn≤1 000 000)$$。
下面的每个$$Q$$行包含一个格式如下的查询:
* 第一行的数字是集合{$$1,2,3,4$$}中的查询类型$$T$$。
* 如果查询T的类型是$$1$$或$$2$$，后面有两个不同的整数$$A$$和$$B(1≤A, B≤N)$$，代表了替换$$(A, B)$$。
### 输出格式:
对于类型为$$3$$或$$4$$的每个查询，在其单独的行中输出答案。
查询类型$$3$$的答案是“$$DA$$”(克罗地亚语表示“是”)或“$$NE$$”(克罗地亚语表示“否”)，没有引号，而查询类型$$4$$的答案是任务中的一个非负整数。
### 得分:
在占总分$$50$$%的测试用例中，它将保持$$N$$, $$Q≤1 000$$。
### 输入样例1:
in
3 5
1 3 2
4
3
2 2 3
4
3
### 输出样例1:
out
1
NE
0
DA
### 输入样例2:
in
5 5
4 2 1 4 4
3 4
1 1 3
3
4
### 输出样例2:
out
NE
1
DA
0
### 输入样例3:
in
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:
out
NE
2
NE
1
3
DA
答案：若无答案欢迎评论
此外，他设想了一套允许的替换。如果一对$$(X, Y)$$是允许替换集合的成员，$$Dominik$$可以交换数组$$p$$中$$X$$和$$Y$$位置的数字。
$$Marin$$给$$Dominik Q$$查询，每个都是以下类型之一:
1. 交换位置$$A$$和$$B$$的数字。
2. 将对$$(A, B)$$添加到允许替换的集合中。$$Marin$$可以给出一对$$(A, B)$$它已经在允许替换的集合中了。
3.看看是否有可能只使用允许的替换对数组进行排序?替换可以以任意顺序使用，并且每个替换可以进行任意次数。
4.如果仅使用允许的替换就可以将位置$$a$$的数字转移到位置$$B$$，那么我们将这对位置$$(a, B)$$连接起来。我们称与位置$$A$$相关的所有位置的集合为$$A$$的云。如果从云中的每个位置$$j$$都有可能使用一系列允许的替换来实现$$p_{j} = q_{j}$$，那么云就是好的。
你必须回答有多少对不同的位置$$(A, B)$$存在，使其成立：
a.位置$$a$$和位置$$B$$没有链接
b. $$A$$云不好，$$B$$云也不好
c.如果我们在允许替换的集合中加入一对$$(A, B)$$， $$A$$的云(通过连接$$A$$的云和$$B$$的云)就会变得很好。
请注意：配对$$(A, B)$$和$$(B, A)$$被认为是相同的一对。
### 输入格式:
第一行输入包含整数$$N$$和$$Q(1≤N, Q≤1 000 000)$$。
输入的第二行包含$$N$$个整数$$p1，…，pn(1≤p1，…，pn≤1 000 000)$$。
下面的每个$$Q$$行包含一个格式如下的查询:
* 第一行的数字是集合{$$1,2,3,4$$}中的查询类型$$T$$。
* 如果查询T的类型是$$1$$或$$2$$，后面有两个不同的整数$$A$$和$$B(1≤A, B≤N)$$，代表了替换$$(A, B)$$。
### 输出格式:
对于类型为$$3$$或$$4$$的每个查询，在其单独的行中输出答案。
查询类型$$3$$的答案是“$$DA$$”(克罗地亚语表示“是”)或“$$NE$$”(克罗地亚语表示“否”)，没有引号，而查询类型$$4$$的答案是任务中的一个非负整数。
### 得分:
在占总分$$50$$%的测试用例中，它将保持$$N$$, $$Q≤1 000$$。
### 输入样例1:
in
3 5
1 3 2
4
3
2 2 3
4
3
### 输出样例1:
out
1
NE
0
DA
### 输入样例2:
in
5 5
4 2 1 4 4
3 4
1 1 3
3
4
### 输出样例2:
out
NE
1
DA
0
### 输入样例3:
in
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:
out
NE
2
NE
1
3
DA
答案：若无答案欢迎评论