Description

This is a template problem.

You need to maintain an undirected simple graph (that is, an undirected graph with no self-loops and no multiple edges). You are required to add an edge, delete an edge, and query whether two vertices are connected.

$0.$: Add an edge. It is guaranteed that it does not exist.
$1.$: Delete an edge. It is guaranteed that it exists.
$2.$: Query whether two vertices are connected.

To keep the solution online, this problem uses a special input method.

Assume you maintain a variable $\text{last}$, with initial value $0$.

For each input vertex $x$, the actual vertex index used in the query or modification is $x \text{ xor } \text{last}$, where $\text{xor}$ is the bitwise XOR operation.

After decoding each query $u,v$, if they are connected, then $\text{last}$ will be updated to $u$; otherwise it will be updated to $v$.

Input Format

The first line contains two integers $n,m$.

The next $m$ lines each contain three integers $\text{op},x,y$. $\text{op}$ denotes the operation number.

Output Format

For each query with $op=2$, output one line Y or N, indicating whether the two vertices are connected.

200 5
2 123 127
0 4 0
2 4 0
1 4 0
2 0 4

N
Y
N

4 10
0 1 2
0 2 3
0 3 1
2 1 4
0 0 7
2 5 0
1 3 2
2 0 5
1 0 2
2 0 5

N
Y
Y
N

Hint

Due to the addition of hack testdata, the data distribution is not as described below. The following is for reference only.

For test point $1$, $n \leq 200,m \leq 200$.

For test point $2$, $n=5,m \leq 30$.

For test point $3$, $n=10,m \leq 1000$, and the number of queries is $\geq 900$.

For test point $4$, $n=300,m \leq 50000$.

For test point $5$, $n=5000,m \leq 200000$, there is no operation $1$, and about $70 \%$ are operation $2$.

For test point $6$, $n=5000,m \leq 200000$, there is no operation $1$, and about $70 \%$ are operation $0$.

For test point $7$ and $8$, $n=100,m \leq 500000$.

For test point $9$, $n=5000,m \leq 500000$, the graph is a tree, and its diameter is $\leq 30$.

For test point $10$, $n=5000,m \leq 500000$, the graph is a tree, and the degree of each vertex is $\leq 10$.

There is also some additional testdata with guarantees $n \leq 5000,m \leq 500000$.

Translated by ChatGPT 5