P3854 [TJOI2008] Communication Network Destruction

Due to conflicts over resources, countries $A$ and $B$ are on the verge of war. Country $A$'s intelligence agency has obtained the layout of country $B$'s communication network, where each city is a vertex, and some pairs of vertices are connected by undirected edges, indicating direct bidirectional communication between those cities. Country $A$ plans to strike first by destroying an intermediate city $M$ with nuclear weapons to sever the connection between two important cities $S$ and $T$ in country $B$. That is, after removing vertex $M$ from the graph, $S$ and $T$ become disconnected. However, since country $B$'s defenses are strong, such a nuclear strike can succeed only once and can destroy only one city.

The leaders of country $A$ have proposed many strategies. As the chief computer scientist of country $A$, your task is to write a program to determine whether each strategy is feasible.

The first line contains two integers $N$ and $M$, representing the number of cities in country $B$ and the number of pairs of cities that can communicate directly. The next $M$ lines each contain two integers $C_i$ and $D_i$, $1\leq C_i,D_i \leq N$ and $C_i \neq D_i$, indicating that cities $C_i$ and $D_i$ can communicate directly. It is guaranteed that each pair $(C_i,D_i)$ appears at most once. The next line contains an integer $Q$, representing the number of strategies proposed by the leaders of country $A$. The next $Q$ lines each contain three integers $S_i, T_i, M_i$ ($1 \leq S_i,T_i,M_i\leq N$, and $M_i, S_i, T_i$ are pairwise distinct), indicating that this strategy attempts to sever communication between $S_i$ and $T_i$ by destroying $M_i$.

Output $Q$ lines, each indicating whether the corresponding strategy is feasible. If, after destroying $M_i$, $S_i$ and $T_i$ cannot communicate, then the strategy is feasible and you should output $\mathtt{yes}$ on the $i$-th line; otherwise, output $\mathtt{no}$.

For $30\%$ of the testdata, $1 \leq N \leq 100,1 \leq Q \leq 100$. For $100\%$ of the testdata, $1 \leq N \leq 20000,1\leq M\leq 100000,1 \leq Q \leq 100000$. It is guaranteed that the original graph is connected. Translated by ChatGPT 5