题目描述

给出一个包含正整数的数组P（p1,…,pn），并假设数组P经过排序后变成数组Q(q1,…,qn)。定义合法替换集合，如果整数对（X，Y）属于合法交换集合，则表示你可以交换数组p中位置X和位置Y的元素。 现在有Q个操作（询问），询问分为以下四种类型：

1.  交换位置A和位置B的元素
   

2.  将整数对（A，B）加入到合法交换集合
   

3.  询问是否能通过合法交换集合中的操作，将数组P进行排序。（注意：过程中可以以任何顺序执行交换操作，并且每个交换操作可以执行任意多次）
   

4.  定义位置对（A，B）是相连的当且仅当位置A的元素可以仅通过合法交换集合中的操作移动到位置B。
   

定义所有和位置A相连的位置组成的集合为A的群集。如果对于每一个在A的群集中的位置j，都能通过一系列合法交换集合中的操作使得pj=qj，则称A的群集是良好的。 你需要回答，有多少对不同的位置对（A，B）满足： a) 位置A和位置B是不相连的 b) A的群集和B的群集都不是良好的 c) 如果我们将位置对（A，B）加入到合法交换集合中，A的群集将变成良好的。 注意：在计算时，位置对（A，B）和位置对（B，A）被视为不同的位置对。 输入 第一行两个正整数，N和Q（1<=N, Q<=1,000,000） 第二行包含N个正整数p1，…，pn（1<=p1,…,pn<=1,000,000） 接下来Q行，每行表示一个操作： l 每行第一个数字表示操作的种类，（1，2，3或4） l 如果操作种类是1或2，后面紧接着两个正整数A，B（1<=A,B<=N）表示位置对（A，B） 输出 对于每一个询问（种类为3、4的操作），输出一行作为询问的答案。 对于种类为3的询问的答案输出“YES”或“NO”（不包含双引号）。“YES”表示能通过合法交换集合的操作将数组P排序，“NO”则表示不能。 对于种类为4的询问输出，输出一个非负整数表示对应的答案。 样例输入 3 5 1 3 2 4 3 2 2 3 4 3 样例输出 1 NO 0 YES 提示

【样例解释1】

第一个询问答案是1，因为只有位置对(2,3)符合所有的条件，第二个询问答案是NO，因为交换集合为空，数字2和3没有办法交换到正确位置，在第三次操作后，我们把位置对(2,3)加入到交换集合中，第四次操作(询问)答案为0因为2和3已经相连，第五次操作(询问)答案是YES，因为可以通过位置对(2,3)把数组排好序。

【样例输入2】

5 5

4 2 1 4 4

3

4

1 1 3

3

4

【样例输出2】

NO

1

YES

0

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

NO

2

NO

1

3

YES

【数据规模和约定】

50%的数据满足N,Q<=1000。 你的任务是写一个程序，输入砖块数N，打印出有多少种不同的摆法。