P5489 EntropyIncreaser 与 动态图

话说 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](https://www.baidu.com/link?url=bhG_De1gZYsqrIq7dkhgGj8vP87xSSyoIwk0-5p1fyKmf58cznvq0oYJg0XGoyKNpuGk7EsvjUnyvgJ19_ZA3PhoMJ3hIufHZ5GXh1OaIoS&wd=&eqid=ab26bc160004324d000000035d1ed64e)

无

无

~~题目背景为真实事件~~ ### 样例说明： 实际操作为： ```cpp 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$