4. 通讯网络

【题目描述】

K市有 $N$ 个房屋，编号从 $1$ 到 $N$。每条电话线连接两栋不同的房屋，所有曾经存在过的电话线都不会形成回路（就像树一样）。

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

$Q$ 个操作，操作格式如下：

• 1 x y：在房屋 $x$ 和 $y$ 之间添加一条电话线。保证之前没有在 $x$ 和 $y$ 之间添加过电话线。
• 2 x y：移除房屋 $x$ 和 $y$ 之间存在的电话线。
• 3 t：计算在最后 $t$ 个操作这一段时间内至少有一个时刻能互相通话的房屋对数。更准确地说，记 Gq 为第 $q$ 个操作之后 K市的状态，G0 为没有任何操作之前的状态。如果是第 $s$ 个操作，则计算在 Gs−t,Gs−t+1,…,Gs 这 $t+1$ 个状态中的至少一个状态中能够互相通话的房屋对数。

部分测试用例会被加密。对于加密的测试用例，参数 $x$，$y$ 和 $t$ 会和上一个类型为 $3$ 的查询的答案进行异或等于（C++ 中的 ^=）操作（如果还没有过类型为 $3$ 的查询，则认为上一个答案为 $0$）。

【输入格式】

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

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

接下来的 $Q$ 行包含如上所述的操作。

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

【样例输出1】

0
1
3
3
1
3
3
5

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

【样例输出2】

0
1
3
3
1
3
3
5

【样例说明】

大样例

【数据规模与约定】

【来源】

在此键入。