Background

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.

Problem Description

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.

Input Format

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.

Output Format

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

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

Hint

The background story is a real event.

Sample Explanation

The actual operations are:

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