为了赢得最艰难的战斗,米尔恰为他的军队想出了一个伟大的战略。他有$$$n$$$士兵,并决定以某种方式将他们安排在营地中。每个士兵必须属于一个阵营,并且 $$$x$$$ 轴上的每个整数点(在点 $$$\cdots, -2, -1, 0, 1, 2, \cdots$$$ 处)都有一个阵营。
该策略由 $$$m$$$ 条件组成。条件 $$$i$$$ 告诉士兵 $$$a_i$$$ 应该属于一个位于 $$$b_i$$$ 所属营地前面 $$$d_i$$$ 米的营地。 (如果 $$$d_i < 0$$$,则 $$$a_i$$$ 的营地应位于 $$$b_i$$$ 营地后面 $$$-d_i$$$ 米处。)
现在,米尔恰想知道是否存在尊重这一条件的士兵分区,他请求你的帮助!如果存在满足所有 $$$m$$$ 条件的 $$$n$$$ 士兵分区,则回答“是”,否则回答“否”。
请注意,两个不同的士兵可能会被安置在同一个营地中。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
每个测试用例的第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq m \leq n$$$) — 分别是士兵数量和条件数量。
接下来是 $$$m$$$ 行,每行包含 $$$3$$$ 整数: $$$a_i$$$, $$$b_i$$$, $$$d_i$$$ ($$$a_i \neq b_i$$$; $$$1 \leq a_i, b_i \leq n$$$; $$$-10^9 \leq d_i \leq 10^9$$$) — 表示语句中解释的条件。请注意,如果 $$$d_i$$$ 为正数,则 $$$a_i$$$ 应位于 $$$b_i$$$ 前面 $$$d_i$$$ 米处,如果为负值,则 $$$a_i$$$ 应位于 $$$b_i$$$ 后面 $$$-d_i$$$ 米处。
请注意,所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果 $$$n$$$ 士兵的排列满足所有 $$$m$$$ 条件,则输出“YES”,否则输出“NO”。
示例
输入 #1
4 5 3 1 2 2 2 3 4 4 2 -6 6 5 1 2 2 2 3 4 4 2 -6 5 4 4 3 5 100 2 2 1 2 5 1 2 4 4 1 1 2 3
输出 #1
YES NO NO YES
注意
对于第一个测试用例,我们可以通过以下方式将士兵划分为营地:士兵:
- 士兵 $$$1$$$ 在营地中,坐标 $$$x = 3$$$。
- 士兵 $$$2$$$ 在营地中,坐标 $$$x = 5$$$。
- 士兵 $$$3$$$ 在营地中,坐标 $$$x = 9$$$。
- 士兵 $$$4$$$ 在营地中,坐标 $$$x = 11$$$。
对于第二个测试用例,不存在可以同时满足所有约束的分区。
对于第三个测试用例,没有满足所有约束的分区,因为我们得到了关于同一对的矛盾信息。
对于第四个测试用例,为了满足唯一条件,可能的分区是:
- 士兵 $$$1$$$ 在营地中,坐标 $$$x = 10$$$。
- 士兵 $$$2$$$ 在营地中,坐标 $$$x = 13$$$。
- 士兵 $$$3$$$ 在营地中,坐标 $$$x = -2023$$$。
- 士兵 $$$4$$$ 在营地中,坐标 $$$x = -2023$$$。