Background

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.

Problem Description

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.

Input Format

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 Format

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

5 6
1 2
1 3
2 3
3 4
3 5
4 5
3
1 5 3
1 5 4
4 5 3

yes
no
no

Hint

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