Dynamic Undirected Graph Online Queries

This is a template problem.

You need to maintain a simple undirected graph (i.e. no self‐loops and no multiple edges). You are required to support the following operations:

• 0: Add an edge. It is guaranteed that the edge does not exist.
• 1: Delete an edge. It is guaranteed that the edge exists.
• 2: Query whether two nodes are connected.

To ensure a linear processing time, the input is given in an encoded manner. Assume you maintain a variable \(last\) initially equal to 0. For each read node \(x\), the actual node is \(x \oplus last\) (where \(\oplus\) denotes the bitwise XOR operation).

Furthermore, for each decoded query (of type 2) with nodes \(u,v\): if they are connected then update \(last = u\), otherwise update \(last = v\). For each query operation, output YES if \(u\) and \(v\) are connected and NO otherwise.

The graph is 0-indexed; the first line of input contains two integers \(n\) and \(q\), representing the number of nodes and the number of operations. The following \(q\) lines each contain three integers: the operation type and two parameters. For each parameter, decode it by XORing with the current \(last\) value.

Note: There is a guarantee that all operations are valid according to the description.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \leq n, q \leq \textrm{constraints})\) representing the number of nodes and the number of operations.

Each of the next \(q\) lines contains three integers: op x y. For each integer \(x\) (or \(y\)), the actual value is computed as \(x \oplus last\) (or \(y \oplus last\)), where \(last\) is initially 0 and is updated as described after each query operation (when op == 2).

\(op\) can be:

• 0: add an edge between the two decoded nodes.
• 1: delete an edge between the two decoded nodes.
• 2: query if the two decoded nodes are connected.

It is guaranteed that the add/delete operations are valid and that the graph is simple and undirected (nodes are numbered from 0 to \(n-1\)).

outputFormat

For each query operation (when op == 2), output a single line containing YES if the two queried nodes are connected, or NO otherwise.

sample

4 5
0 1 2
2 1 3
0 3 0
0 1 3
2 2 0

NO
YES

</p>