P5489 EntropyIncreaser and Dynamic Graph

It is said that when NaCly_Fish was having a meal with $\mathsf E \color{red}\mathsf{ntropyIncreaser}$, he asked her a question: “Given an undirected graph that supports dynamic edge insertions, how do we find the number of articulation points between two vertices?” $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ thought for a few seconds and said: “Isn’t this a super easy problem? You can do it however you want.” Then she explained an algorithm in just a few sentences. But NaCly_Fish still did not understand it. Please teach her how to solve this problem.

There is a graph with $n$ vertices, initially with no edges. There are $q$ operations, of $3$ types, as follows: - `1 u v` means adding an undirected edge between $u$ and $v$. - `2 u v` means querying the number of bridges between $u$ and $v$. - `3 u v` means querying the number of articulation points between $u$ and $v$. In particular, for operations $2$ and $3$, if $u$ and $v$ are not connected, output $-1$. **** To avoid ambiguity, here are the definitions of the number of bridges and articulation points between two vertices: Let $S$ be the intersection of the vertex sets of all paths that contain both $u$ and $v$. Define the number of elements in $S$ as the number of articulation points between $u$ and $v$. Let $T$ be the intersection of the edge sets of all paths that contain both $u$ and $v$. Define the number of elements in $T$ as the number of bridges between $u$ and $v$. **** **This problem is strictly online.** Starting from the second line, in each input, $u,v$ must be XORed with $\text{last}$ to get the actual $u,v$. $\text{last}$ is the answer of the most recent query whose answer is **not $-1$**, and initially $\text{last}=0$. ps: If you do not know what XOR means, see here: [xor](https://www.baidu.com/link?url=bhG_De1gZYsqrIq7dkhgGj8vP87xSSyoIwk0-5p1fyKmf58cznvq0oYJg0XGoyKNpuGk7EsvjUnyvgJ19_ZA3PhoMJ3hIufHZ5GXh1OaIoS&wd=&eqid=ab26bc160004324d000000035d1ed64e).

The first line contains two positive integers $n,q$, representing the number of vertices and the number of operations. The next $q$ lines each contain three integers, describing one operation.

For each operation of type $2$ or $3$, output one line with one integer representing the answer.

~~The background story is a real event.~~ ### Sample Explanation The actual operations are: ```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 ``` ### Constraints For $20\%$ of the testdata, $1\le n,q \le 2000$. For another $30\%$ of the testdata, all operations of type $2$ and $3$ occur after a type $1$ operation. For $100\%$ of the testdata, $1\le n \le 10^5$, $1\le q \le 3\times 10^5$. For type $1$ operations, it is guaranteed that $u\neq v$. By: NaCly_Fish **** Welcome to join the EI Captain fan group. Group number: $747262201$. Translated by ChatGPT 5