← 返回题目列表

Codeforces · 1515/G

G. 凤凰城和里程表

中文机器翻译题面 查看原题

在火城,有 $$$n$$$ 个十字路口和 $$$m$$$ 单向道路。第 $$$i$$$ 条路从十字路口 $$$a_i$$$ 到 $$$b_i$$$,长度为 $$$l_i$$$ 英里。

有 $$$q$$$ 汽车只能沿着这些道路行驶。第 $$$i$$$ 车从十字路口 $$$v_i$$$ 出发,里程表从 $$$s_i$$$ 开始,每行驶一英里就会递增,并在到达 $$$t_i$$$ 时重置为 $$$0$$$。菲尼克斯的任务是沿着一些道路(可能没有)驾驶汽车,并将它们返回到最初的十字路口,里程表显示 $$$0$$$。

对于每辆车,请查明这是否可行。

汽车可以任意多次访问同一条道路或交叉路口。里程表在重置后不会停止计算距离,因此里程表也可以重置任意次数。

输入

输入的第一行包含两个整数 $$$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 < t_i \le 10^9$$$) - 第 $$$i$$$ 的初始交集汽车、第 $$$i$$$ 里程表上的初始号码以及第 $$$i$$$ 里程表重置的号码。

输出

打印 $$$q$$$ 答案。如果第 $$$i$$$ 车的里程表可以通过行驶一些道路(可能没有)并返回其起始交叉路口 $$$v_i$$$ 重置为 $$$0$$$,则打印 YES。否则,打印NO。

示例

输入 #1

4 4
1 2 1
2 3 1
3 1 2
1 4 3
3
1 1 3
1 2 4
4 0 1

输出 #1

YES
NO
YES

输入 #2

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

输出 #2

YES
YES

注意

第一个示例的图示如下:

在第一个查询中,Phoenix 可以开车经过以下城市: $$$1$$$ $$$\rightarrow$$$ $$$2$$$ $$$\rightarrow$$$ $$$3$$$ $$$\rightarrow$$$ $$$1$$$ $$$\rightarrow$$$ $$$2$$$ $$$\rightarrow$$$ $$$3$$$ $$$\rightarrow$$$ $$$1$$$。里程表将重置 $$$3$$$ 次,但最后显示 $$$0$$$。

在第二个查询中,我们可以表明没有办法将里程表重置为 $$$0$$$ 并返回到路口 $$$1$$$。

在第三次查询中,里程表已经显示$$$0$$$,因此无需行驶任何道路。

下面是第二个示例的图示: