Description

After much effort, the Martian Cat finally reaches Pluto. There are $N$ cities and $M$ undirected edges. The Martian Cat plans to visit the Pluto Rabbit and has heard that some cream puffs have fallen on certain edges, so he wants to collect some as a gift. However, the Martian Cat’s aura conflicts with Pluto: once he traverses an edge, that edge can no longer be used. If the Pluto Rabbit cannot get any cream puffs, they won’t be happy. Given the positions of the Martian Cat and the Pluto Rabbit, determine whether the Pluto Rabbit can get a cream puff, i.e., whether there exists a trail from $S$ to $T$ that passes through at least one edge with a cream puff.

Input Format

The first line contains $N, M$, the number of vertices and edges.

Each of the next $M$ lines contains $X, Y, Z$, indicating an undirected edge between $X$ and $Y$; $Z = 1$ means there is a cream puff on this edge, and $Z = 0$ means there is not.

The next line contains $Q$, the number of queries.

Each of the following $Q$ lines contains $S, T$, the positions of the Martian Cat and the Pluto Rabbit.

Output Format

For each query, output YES or NO.

6 7
1 2 0
2 3 0
3 1 0
3 4 1
4 5 0
5 6 0
6 4 0
1
1 6

YES

Hint

The graph is connected.

Translated by ChatGPT 5