题目描述

为了赢得他最艰难的战斗，Mircea 为他的军队想出了一个绝妙的策略。他有 $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$ 米的位置。）

现在，Mircea 想知道是否存在一种士兵的分配方式，能够满足所有条件。他请求你的帮助！如果存在一种分配方式使得 $n$ 名士兵的安排满足所有 $m$ 个条件，请输出 "YES"；否则输出 "NO"。

注意，不同的士兵可以被安排在同一个营地。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq n$），分别表示士兵数量和条件数量。

接下来 $m$ 行，每行包含三个整数 $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$ 米处；如果 $d_i$ 为负，则 $a_i$ 应在 $b_i$ 后方 $-d_i$ 米处。

注意，所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果存在一种士兵的安排方式满足所有条件，输出 "YES"；否则输出 "NO"。

样例

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

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$ 的营地。

由 ChatGPT 4.1 翻译

来源

Codeforces 1850H，英文题名 The Third Letter。