题目描述

译自 CCO 2024 Day2 T3「Telephone Plans」。

CCO 国现在由唯一的电话服务商「多米通」提供服务。CCO 国有 $N$ 个房屋，编号从 $1$ 到 $N$。每条电话线连接两栋不同的房屋，所有曾经存在过的电话线都不会形成回路（就像树一样）。

但是，这些电话线有些问题，每条电话线只能在一段时间内使用。如果在某个时刻，房屋之间存在着由电话线连接的路径，那么这两个房屋就可以互相通话。

我们想要处理 $Q$ 个查询，查询格式如下：

• 1 x y：在房屋 $x$ 和 $y$ 之间添加一条电话线。保证之前没有在 $x$ 和 $y$ 之间添加过电话线。
• 2 x y：移除房屋 $x$ 和 $y$ 之间存在的电话线。
• 3 t：计算在最后 $t$ 个查询这一段时间内至少有一个时刻能互相通话的房屋对数。更准确地说，记 $G_q$ 为第 $q$ 个查询之后 CCO 国的状态，$G_0$ 为没有任何查询之前的状态。如果是第 $s$ 个查询，则计算在 $G_{s-t},G_{s-t+1}, \ldots ,G_s$ 这 $t + 1$ 个状态中的至少一个状态中能够互相通话的房屋对数。

部分测试用例可能会被加密。对于加密的测试用例，参数 x、y 和 t 会被当前查询编号和上一个类型为 3 的查询的答案进行异或运算（如果还没有过类型为 3 的查询，则参数保持不变）。

输入格式

第一行输入一个数字 $E\ (E \in\{0,1\})$。$E=0$ 表示输入没有加密，$E=1$ 表示输入加密。

第二行包含两个空格分隔的整数 $N$ 和 $Q$，分别代表 CCO 国的房屋数量和查询数量。

接下来的 $Q$ 行包含如上所述的查询。

对于第 $q\ (1 \leq q \leq N)$ 个查询，保证解密后（如果 $E=1$）：对于类型 1 和 2 的查询，$1 \leq x, y \leq N$；对于类型 3 的查询，$0 \leq t \leq q$。

输出格式

对于每个类型为 3 的查询，单独一行输出查询的答案。

0
4 12
3 0
1 1 2
3 0
1 1 3
3 0
3 5
2 2 1
3 0
3 8
1 1 4
3 0
3 11

0
1
3
3
1
3
3
5

该测试用例没有加密。

对于第 $1$ 个查询，没有任何房屋对可以互相通话。
对于第 $3$ 个查询，只有房屋 $1$ 和 $2$ 可以互相通话。
对于第 $5$ 个查询，可以互相通话的房屋对有：$\{(1,2), (1,3), (2,3)\}$。第 $6$ 个查询同理。
对于第 $8$ 个查询，只有房屋 $1$ 和 $3$ 可以互相通话。
对于第 $9$ 个查询，存在某个时刻可以让 $\{(1,2), (1,3), (2,3)\}$ 这三个房屋对互相通话。
对于第 $11$ 个查询，可以互相通话的房屋对有 $\{(1, 3), (1, 4), (3, 4)\}$。
对于第 $12$ 个查询，在当前查询之前的所有时间点，都可以互相通话的房屋对有 $\{(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)\}$。

1
4 12
3 0
1 1 2
3 0
1 0 2
3 1
3 6
2 1 2
3 3
3 9
1 2 7
3 3
3 8

0
1
3
3
1
3
3
5

样例 1 的加密版本。

数据范围与提示

子任务	分值	$N$ 的限制	$Q$ 的限制	是否加密
$1$	$12$	$1 \leq N \leq 30$	$1 \leq Q \leq 150$	否
$2$	$8$			是
$3$	$16$	$1 \leq N \leq 2000$	$1 \leq Q \leq 6000$	否
$4$	$8$			是
$5$	$16$	$1 \leq N \leq 10^5$	$1 \leq Q \leq 3\times 10^5$	否
$6$	$20$			是
$7$	$20$	$1 \leq N \leq 5\times 10^5$	$1 \leq Q \leq 1.5\times 10^6$