4171. 「CCO 2024」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 Q)$ 个查询，保证解密后（如果 $E = 1$）：

• 对于类型 $1$ 和 $2$ 的查询，$1 \leq x, y \leq N$
• 对于类型 $3$ 的查询，$0 \leq t \leq q$

输出格式

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

样例 1

输入

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)\}$。

样例 2

输入

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		$1 \leq N \leq 5 \times 10^5$	$1 \leq Q \leq 1.5 \times 10^6$