题目背景

翻译自 CCO 的 2024P6题。

题目描述

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$ 的查询的答案进行异或等于（C++ 中的 ^=）操作（如果还没有过类型为 $3$ 的查询，则认为上一个答案为 $0$）。

输入格式

第一行输入一个数字 $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
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

提示