Dynamic Graph Cut Queries with Online XOR

You are given an undirected graph with \(n\) vertices (numbered from 1 to \(n\)) and no edges initially. Then, you are given \(q\) operations. Moreover, the problem is online: starting from the second operation line, the two parameters \(u\) and \(v\) in every operation are given in an encoded form and need to be decoded by XORing them with a variable \(last\). Initially \(last = 0\), and after every query (operations of type 2 or 3) whose answer is not \(-1\), update \(last\) to that answer.

The operations are of three types:

• 1 u v: Add an undirected edge between vertices \(u\) and \(v\).
• 2 u v: Query the number of cut edges between \(u\) and \(v\).
• 3 u v: Query the number of cut vertices between \(u\) and \(v\).

Important notes:

1. If \(u\) and \(v\) are not connected, output \(-1\).
2. For queries of type 2 and 3, we define the answer as follows. Consider the set of all simple paths between vertices \(u\) and \(v\). Let \(S\) be the intersection of the vertex sets of all these paths, and let \(T\) be the intersection of the edge sets of all these paths. Then:</p>
   • The cut vertex count is defined as \(|S|\). Notice that since every \(u\)–\(v\) path includes \(u\) and \(v\), if \(u \neq v\) then at minimum \(S\) contains \(u\) and \(v\). In particular, if there exists an alternate path which bypasses all intermediate vertices then \(S = \{u, v\}\) and the answer is 2.
   • The cut edge count is defined as \(|T|\). For example, if the path between \(u\) and \(v\) is unique the answer is the number of edges on that path.
3. For the query of type 3, if \(u = v\) then output 1.
4. Online XOR: For every operation (from the second line of operations onward) the given \(u\) and \(v\) must be replaced by \(u \oplus last\) and \(v \oplus last\) respectively, where \(\oplus\) denotes the bitwise XOR operator.

Input/Output online: The input is read online and your program should process each operation in order.

Note: It is guaranteed that after decoding, all vertex numbers lie in the range \([1, n]\).

inputFormat

The first line contains two integers \(n\) and \(q\) --- the number of vertices and the number of operations.

The following \(q\) lines each describe an operation in one of the following formats:

• 1 u v
• 2 u v
• 3 u v

Note: For every operation from the second operation onward, the given values of \(u\) and \(v\) are encoded. They must be decoded by computing \(u \oplus last\) and \(v \oplus last\), where \(last\) initially is 0 and is updated to the answer of the last query (type 2 or 3) that returned a value different from \(-1\).

outputFormat

For each query operation (i.e. operations of type 2 and 3), output a single integer on a new line, which is the required answer. For type 2, output the number of cut edges between \(u\) and \(v\); for type 3, output the number of cut vertices between \(u\) and \(v\) (remember that if \(u \neq v\), the vertices \(u\) and \(v\) are always included in every path). If \(u\) and \(v\) are not connected, output \(-1\).

sample

7 7
1 1 2
1 2 3
2 1 3
1 3 1
3 1 3
1 4 5
2 4 5

2
2
1