Problem Background

This is an unofficial, unmaintained mirror of LOJ #122. The original problem author is EtaoinWu, and the original uploader on this site is unknown. The data for this mirror problem is not guaranteed to be up-to-date, so it is recommended to practice on LOJ.

Problem Description

This is a template problem.

You need to maintain an undirected simple graph (i.e., an undirected graph without self-loops or multiple edges). You are required to add or delete an edge and query whether two points 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 points are connected.

To ensure the linearity of the solution, the input is read in a special way.

Assume you maintain a variable $\text{last}$, initialized to $0$.

For each input node $x$, the actual node number for the query or modification is $x \text{ xor } \text{last}$, where $\text{xor}$ is the binary XOR operation.

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

Input Format

The first line of input contains two numbers $n, m$.

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

Output Format

For each query with $op=2$, output a line containing Y or N to indicate whether the two nodes are connected.

Sample Input and Output

Sample Input #1

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

Sample Output #1

N
Y
N

Sample Input #2

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

Sample Output #2

N
Y
Y
N

Notes

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

• For data point $1$, $n \leq 200, m \leq 200$
• For data point $2$, $n=5, m \leq 30$
• For data point $3$, $n=10, m \leq 1000$, with queries $\geq 900$ times.
• For data point $4$, $n=300, m \leq 50000$
• For data point $5$, $n=5000, m \leq 200000$, with no operation $1$, about $70\%$ are operation $2$.
• For data point $6$, $n=5000, m \leq 200000$, with no operation $1$, about $70\%$ are operation $0$.
• For data points $7$ and $8$, $n=100, m \leq 500000$
• For data point $9$, $n=5000, m \leq 500000$, the graph is a tree with diameter $\leq 30$.
• For data point $10$, $n=5000, m \leq 500000$, the graph is a tree with each node degree $\leq 10$.

Additional data guarantees $n \leq 5000, m \leq 500000$.

见题面 Input 部分

见题面 Output 部分