P2147 [SDOI2008] Cave Exploration

Huihui is enthusiastic about cave exploration. One day, following a map, he arrived at an area marked as JSZX, which is a cluster of caves. After a preliminary survey, Huihui found that this area consists of $n$ caves (numbered from $1$ to $n$) and several tunnels, where each tunnel connects exactly two caves. If two caves can be connected in order by one or more tunnels, then these two caves are said to be connected, and the sequence of tunnels connected in order is called a path between the two caves. The caves are very solid and cannot be destroyed, but the tunnels are unstable and often change due to external influences. For example, according to the monitoring device, sometimes a tunnel appears between cave $123$ and cave $127$, and sometimes this tunnel is destroyed for some odd reason. Huihui has a monitoring device that can display every change to the tunnels on the terminal at his side: - If a tunnel appears between cave $u$ and cave $v$ (guaranteed that it did not previously exist), the terminal displays the instruction `Connect u v`. - If the tunnel between cave $u$ and cave $v$ is destroyed (guaranteed that it previously existed), the terminal displays the instruction `Destroy u v`. After long and arduous manual calculations, Huihui discovered a strange phenomenon: no matter how the tunnels change, at any time there is at most one path between any two caves. Therefore, he is convinced that this is governed by some essential rule. He kept working day and night in front of the terminal, trying to study this rule through the changes in the tunnels. However, one day he finally collapsed among the piles of scratch paper... He smashed the terminal onto the ground (the terminal is also solid and cannot be destroyed) and turned to you for help, saying: “Please write this program for me.” Huihui wants to be able to issue the instruction `Query u v` at any time to ask the monitor whether cave $u$ and cave $v$ are currently connected. Now you need to write a program to answer each query. It is known that before the first instruction appears, there are no tunnels in the JSZX cave cluster.

The first line contains two positive integers $n$ and $m$, representing the number of caves and the number of instructions shown on the terminal. The following $m$ lines describe the instructions that appear on the terminal in order: - Each line begins with a string $S$ indicating the type of instruction. - Then there are two integers $u, v$, representing the indices of the two caves.

For each `Query` instruction, output whether cave $u$ and cave $v$ are connected: output `Yes` if connected, otherwise output `No`.

Constraints: - For $ (i \times 10)\% $ of the testdata, $n \le i \times 10^3$, $m \le 2 i \times 10^4$. - For $100\%$ of the testdata, $1 \le n \le 10^4$, $1 \le m \le 2 \times 10^5$, $1 \le u, v \le n$, and all instructions are valid. The I/O scale is large. It is recommended that C/C++ users use `scanf` and `printf` for I/O to avoid timeouts. @namespace_std added a set of hack testdata on 2019.12.1. Translated by ChatGPT 5