P5247 [Template] Dynamic Graph Connectivity

This is an unofficial, **unmaintained** mirror of [LOJ #122](https://loj.ac/problem/122). The original problem setter is EtaoinWu, and the original uploader on this site is unknown. The testdata of this mirror is not guaranteed to be the latest, so it is recommended to practice on LOJ.

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$.

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.

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

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