CF1515G.Phoenix and Odometers

In Fire City, there are $n$ intersections and $m$ one-way roads. The $i$-th road goes from intersection $a_i$ to $b_i$ and has length $l_i$ miles.

There are $q$ cars that may only drive along those roads. The $i$-th car starts at intersection $v_i$ and has an odometer that begins at $s_i$, increments for each mile driven, and resets to $0$ whenever it reaches $t_i$. Phoenix has been tasked to drive cars along some roads (possibly none) and return them to their initial intersection with the odometer showing $0$.

For each car, please find if this is possible.

A car may visit the same road or intersection an arbitrary number of times. The odometers don't stop counting the distance after resetting, so odometers may also be reset an arbitrary number of times.

在火焰城中有 $n$ 个路口和 $m$ 条单向道路。第 $i$ 条道路从路口 $a_i$ 指向 $b_i$，长度为 $l_i$ 英里。

共有 $q$ 辆汽车，它们只能沿这些道路行驶。第 $i$ 辆汽车从路口 $v_i$ 出发，其里程表初始读数为 $s_i$，每行驶一英里便加 $1$，当读数达到 $t_i$ 时自动重置为 $0$。凤凰的任务是驾驶每辆汽车沿若干道路（可以不经过任何道路）行驶，并最终使其返回出发路口，且此时里程表读数恰好为 $0$。

对每辆汽车，请判断该任务是否可行。

一辆汽车可任意多次经过同一条道路或同一个路口。里程表在重置后不会停止计数，因此里程表也可被重置任意多次。

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^5$) — the number of intersections and the number of roads, respectively.

Each of the next $m$ lines contain three integers $a_i$, $b_i$, and $l_i$ ($1 \le a_i, b_i \le n$; $a_i \neq b_i$; $1 \le l_i \le 10^9$) — the information about the $i$-th road. The graph is not necessarily connected. It is guaranteed that between any two intersections, there is at most one road for each direction.

The next line contains an integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of cars.

Each of the next $q$ lines contains three integers $v_i$, $s_i$, and $t_i$ ($1 \le v_i \le n$; $0 \le s_i \lt t_i \le 10^9$) — the initial intersection of the $i$-th car, the initial number on the $i$-th odometer, and the number at which the $i$-th odometer resets, respectively.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$；$1 \le m \le 2 \cdot 10^5$），分别表示交叉路口的数量和道路的数量。

接下来的 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $l_i$（$1 \le a_i, b_i \le n$；$a_i \neq b_i$；$1 \le l_i \le 10^9$），描述第 $i$ 条道路的信息。该图不一定连通。保证任意两个交叉路口之间，每个方向至多存在一条道路。

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示汽车的数量。

接下来的 $q$ 行，每行包含三个整数 $v_i$、$s_i$ 和 $t_i$（$1 \le v_i \le n$；$0 \le s_i \lt t_i \le 10^9$），分别表示第 $i$ 辆汽车的初始交叉路口、初始里程表读数以及里程表重置时的数值。

Print $q$ answers. If the $i$-th car's odometer may be reset to $0$ by driving through some roads (possibly none) and returning to its starting intersection $v_i$, print YES. Otherwise, print NO.

输出 $q$ 个答案。如果第 $i$ 辆车的里程表可以通过驶过若干条道路（可以为零条）并返回其起始交叉路口 $v_i$ 而被重置为 $0$，则输出 YES；否则输出 NO。

The illustration for the first example is below:

In the first query, Phoenix can drive through the following cities: $1$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $1$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $1$. The odometer will have reset $3$ times, but it displays $0$ at the end.

In the second query, we can show that there is no way to reset the odometer to $0$ and return to intersection $1$.

In the third query, the odometer already displays $0$, so there is no need to drive through any roads.

Below is the illustration for the second example:

第一个示例的示意图如下：

在第一次查询中，凤凰可以依次经过以下城市：$1$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $1$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $1$。里程表将重置 $3$ 次，但最终显示值为 $0$。

在第二次查询中，可以证明不存在一种方式，使得里程表重置为 $0$ 并同时返回到交叉路口 $1$。

在第三次查询中，里程表当前已显示 $0$，因此无需经过任何道路。

第二个示例的示意图如下：