P11519 [CCO 2024] Telephone Plans

翻译自 [CCO](https://cemc.uwaterloo.ca/resources/past-contests?contest_category=80) 的 [2024P6题](https://dmoj.ca/problem/cco24p6)。

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 Q)$ 个查询，保证解密后（如果 $E=1$）：对于类型 $1$ 和 $2$ 的查询，$1 \leq x, y \leq N$；对于类型 $3$ 的查询，$0 \leq t \leq q$。

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

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