Phoenix and Odometers
Contest: Codeforces Global Round 14
Difficulty rating: 2700
Tags: dfs and similar, graphs, math, number theory

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.

Input format:
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 < 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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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:

Example input:
4 4
1 2 1
2 3 1
3 1 2
1 4 3
3
1 1 3
1 2 4
4 0 1

Example output:
YES
NO
YES

Example input:
4 5
1 2 1
2 3 1
3 1 2
1 4 1
4 3 2
2
1 2 4
4 3 5

Example output:
YES
YES

Editorial:
We can solve for each strongly-connected component independently. From now on, we will assume the graph is strongly-connected.
Define the length of a walk to be the sum of the weights of its edges, modulo $$$MOD$$$, the distance at which the odometer resets. This is different for different queries, but the important thing is some $$$MOD$$$ exists.
If there is a walk from $$$a$$$ to $$$b$$$ with length $$$x$$$, there is a walk from $$$b$$$ to $$$a$$$ with length $$$-x$$$ (for any $$$MOD$$$). To see this, note that since the graph is strongly-connected, there is a path from $$$b$$$ to $$$a$$$. Let its length be $$$y$$$. We can walk from $$$b$$$ to $$$a$$$ and back $$$MOD-1$$$ times and then go to $$$a$$$ for a total length of $$$(MOD)y+(MOD-1) x\equiv -x$$$. Note that this works for any $$$MOD$$$, even if we don't know what it is yet.
We can show that if $$$a$$$ is in a cycle of length $$$x$$$, then $$$b$$$ is in a cycle of length $$$x$$$. Suppose a path from $$$a$$$ to $$$b$$$ has length $$$y$$$. We can go from $$$b$$$ to $$$a$$$, go around the cycle, and go back to $$$b$$$ for a total length of $$$y+x+(-y)=x$$$.
$$$a$$$ is in a cycle of length $$$0$$$. If $$$a$$$ is in a cycle of length $$$x$$$, it is in a cycle of $$$kx$$$ for any integer $$$k$$$. If $$$a$$$ is in a cycle of length $$$x$$$ and a cycle of length $$$y$$$, it is in a cycle of length $$$x+y$$$.
The set of possible cycle lengths of cycles containing vertex $$$a$$$ are exactly the multiples of some number, namely the $$$\gcd$$$ of all possible cycle lengths.
So, if we want to determine all possible cycle lengths, we just need to compute this gcd. Fix an arbitrary spanning tree rooted at $$$r$$$ and denote the length of the tree path from $$$r$$$ to $$$a$$$ by $$$\phi(a)$$$.
If there is an edge of length $$$l$$$ from $$$a$$$ to $$$b$$$, then $$$r$$$ is in a cycle of length $$$\phi(a)+l-\phi(b)$$$. This cycle can be constructed by taking the walk along tree edges from $$$r$$$ to $$$a$$$, across the edge from $$$a$$$ to $$$b$$$, then backwards along tree edges from $$$b$$$ to $$$a$$$.
Thus, we can make any cycles whose length is a multiple of $$$G=\gcd\{\phi(a)+l-\phi(b):(a,b,l)\in E\}$$$. It turns out these are the only possible lengths.
If a walk from $$$a$$$ to $$$b$$$ has length $$$x$$$, then $$$x\equiv \phi(b)-\phi(a)\pmod G$$$. This can be proved by induction on the number of edges in the walk.
Now that we know which cycle lengths are possible, we can answer the queries.
An odometer can be reset if and only if $$$S$$$ plus some multiple of $$$T$$$ is a multiple of $$$G$$$.
An odometer can be reset if and only if $$$S$$$ is a multiple of $$$\gcd(T,G)$$$.
For implementation, the easiest way to get a spanning tree is by DFS. This can be done while computing strongly-connected components.