题目背景

话说 NaCly_Fish 在和 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 吃饭时，问过她一个问题：“一个无向图，支持动态加边，求两点间割点数，怎么做？”

$\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 想了几秒，说：“这不是sb题吗，随便怎么做都行吧。”然后三两句道出了一个算法。

而 NaCly_Fish 还是不会，请你来教教她这题怎么做吧。

题目描述

有一个 $n$ 个点的图，初始没有边。
有 $q$ 个操作，分为 $3$ 种，具体如下：

• 1 u v 表示在 $u,v$ 之间连一条无向边
• 2 u v 表示求 $u,v$ 间的割边数量
• 3 u v 表示求 $u,v$ 间的割点数量

特别地，对于 $2$、$3$ 操作，若 $u,v$ 不连通，则输出 $-1$

为了防止有歧义，这里给出对两点间割边和割点数量的定义：
对于所有包含 $u,v$ 的路径的节点集合之交 $S$ ，定义 $S$ 中的元素数量为 $u,v$ 间的割点数。
对于所有包含 $u,v$ 的路径的边集合之交 $T$ ，定义 $T$ 中的元素数量为 $u,v$ 间的割边数。

本题强制在线。
从第二行开始，每次的输入的 $u,v$ 都需要异或上 $\text{last}$ ，才是实际操作的 $u,v$。
$\text{last}$ 为最近一次答案非 $-1$ 的询问的答案，定义初始 $\text{last}=0$
ps：如果您不知道异或是什么意思，可以看这里：xor

输入格式

第一行两个正整数 $n,q$，表示节点数和操作次数。
接下来 $q$ 行，每行三个整数，表示一次操作。

输出格式

对于每个$2$、$3$ 操作，输出一行一个整数表示答案。

5 10
1 1 2
1 2 3
2 1 3
3 0 1
1 3 1
1 1 6
2 3 7
1 6 7
1 7 1
3 3 6

2
2
-1
3

提示

题目背景为真实事件

样例说明：

实际操作为：

5 10
1 1 2
1 2 3
2 1 3
3 2 3
1 1 3
1 3 4
2 1 5
1 4 5
1 5 3
3 1 4

【数据范围】

对于 $20\%$ 的数据，$1\le n,q \le 2000$ ；
对于另外 $30\%$ 的数据，所有 $2$、$3$ 操作均在 $1$ 操作之后；
对于 $100\%$ 的数据，$1\le n \le 10^5$，$1\le q \le 3\times 10^5$。

对于 $1$ 操作，保证 $u\neq v$。

By：NaCly_Fish

欢迎加入 EI队长粉丝裙，群号：$747262201$