P2416 Cream Puffs

This problem has a space limit of $256$ MB, and the system stack size equals the memory limit.

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.

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.

For each query, output `YES` or `NO`.

| Test point ID | $N \le$ | $M \le$ | $Q \le$ | Special property | | :---------------: | :---------------: | :---------------: | :---------------: | :--------------------: | | $1 \sim 4$ | $1000$ | $N - 1$ | $5 \times 10^4$ | The graph is a tree. | | $5 \sim 8$ | $3 \times 10^5$ | $N - 1$ | $3 \times 10^5$ | None | | $9 \sim 10$ | $20$ | $50$ | $5$ | None | | $11 \sim 14$ | $1000$ | $5000$ | $5 \times 10^4$ | None | | $15 \sim 20$ | $3 \times 10^5$ | $3 \times 10^5$| $3 \times 10^5$ | None | The graph is connected. Translated by ChatGPT 5