310554: CF1850H. The Third Letter
Description
In order to win his toughest battle, Mircea came up with a great strategy for his army. He has $n$ soldiers and decided to arrange them in a certain way in camps. Each soldier has to belong to exactly one camp, and there is one camp at each integer point on the $x$-axis (at points $\cdots, -2, -1, 0, 1, 2, \cdots$).
The strategy consists of $m$ conditions. Condition $i$ tells that soldier $a_i$ should belong to a camp that is situated $d_i$ meters in front of the camp that person $b_i$ belongs to. (If $d_i < 0$, then $a_i$'s camp should be $-d_i$ meters behind $b_i$'s camp.)
Now, Mircea wonders if there exists a partition of soldiers that respects the condition and he asks for your help! Answer "YES" if there is a partition of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.
Note that two different soldiers may be placed in the same camp.
InputThe first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.
The first line of each test case contains two positive integers $n$ and $m$ ($2 \leq n \leq 2 \cdot 10^5$; $1 \leq m \leq n$) — the number of soldiers, and the number of conditions respectively.
Then $m$ lines follow, each of them containing $3$ integers: $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$) — denoting the conditions explained in the statement. Note that if $d_i$ is positive, $a_i$ should be $d_i$ meters in front of $b_i$ and if it is negative, $a_i$ should be $-d_i$ meters behind $b_i$.
Note that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
OutputFor each test case, output "YES" if there is an arrangement of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.
ExampleInput4 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 3Output
YES NO NO YESNote
For the first test case, we can partition the soldiers into camps in the following way: soldier:
- Soldier $1$ in the camp with the coordinate $x = 3$.
- Soldier $2$ in the camp with the coordinate $x = 5$.
- Soldier $3$ in the camp with the coordinate $x = 9$.
- Soldier $4$ in the camp with the coordinate $x = 11$.
For the second test case, there is no partition that can satisfy all the constraints at the same time.
For the third test case, there is no partition that satisfies all the constraints since we get contradictory information about the same pair.
For the fourth test case, in order to satisfy the only condition, a possible partition is:
- Soldier $1$ in the camp with the coordinate $x = 10$.
- Soldier $2$ in the camp with the coordinate $x = 13$.
- Soldier $3$ in the camp with the coordinate $x = -2023$.
- Soldier $4$ in the camp with the coordinate $x = -2023$.
Input
题意翻译
$t$ 组数据。对于每组数据： 第一行给定 $n$ 和 $m$，表示有 $n$ 个人和 $m$ 个要求。每个人都站在数轴上的一个整数点上（可以在负半轴上）。 然后的 $m$ 行，每行一个要求。每个要求包含 $a_i, b_i$ 和 $d_i$，表示第 $a_i$ 个人要站在第 $b_i$ 个人前方的第 $d_i$ 个位置（如果 $d_i$ 是负数，则第 $a_i$ 个人要站在第 $b_i$ 个人后方的第 $-d_i$ 个位置。问是否存在满足要求的方案。 $t \leq 100, \sum n \leq 2e5, m \leq n, -10^9 \leq d_i \leq 10^9$Output
Mircea为了赢得他最艰难的战斗，为他的军队制定了一个伟大的策略。他有n个士兵，并决定以特定的方式在营地中安排他们。每个士兵必须恰好属于一个营地，且x轴上的每个整数点都有一个营地（在点...、-2、-1、0、1、2、...上）。
策略包括m个条件。条件i告诉士兵a_i应该属于一个位于b_i所属营地的d_i米前的营地。（如果d_i < 0，那么a_i的营地应该在b_i的营地的-d_i米后。）Mircea想知道是否存在一个符合所有条件的士兵划分，并请求你的帮助！如果存在一个n个士兵的划分，满足所有m个条件，则回答"YES"，否则回答"NO"。
注意，两个不同的士兵可以放在同一个营地。
**输入数据格式：**
输入的第一行包含一个整数t（1≤t≤100）——测试用例的数量。
每个测试用例的第一行包含两个正整数n和m（2≤n≤2×10^5；1≤m≤n）——士兵的数量和条件的数量。
然后是m行，每行包含3个整数：a_i、b_i、d_i（a_i ≠ b_i；1≤a_i，b_i≤n；-10^9≤d_i≤10^9）——表示题目中解释的条件。注意，如果d_i为正，a_i应该在b_i的d_i米前，如果为负，a_i应该在b_i的-d_i米后。
注意，所有测试用例的n之和不超过2×10^5。
**输出数据格式：**
对于每个测试用例，如果存在一个满足所有m个条件的n个士兵的排列，则输出"YES"，否则输出"NO"。**题目大意：** Mircea为了赢得他最艰难的战斗，为他的军队制定了一个伟大的策略。他有n个士兵，并决定以特定的方式在营地中安排他们。每个士兵必须恰好属于一个营地，且x轴上的每个整数点都有一个营地（在点...、-2、-1、0、1、2、...上）。 策略包括m个条件。条件i告诉士兵a_i应该属于一个位于b_i所属营地的d_i米前的营地。（如果d_i < 0，那么a_i的营地应该在b_i的营地的-d_i米后。）Mircea想知道是否存在一个符合所有条件的士兵划分，并请求你的帮助！如果存在一个n个士兵的划分，满足所有m个条件，则回答"YES"，否则回答"NO"。 注意，两个不同的士兵可以放在同一个营地。 **输入数据格式：** 输入的第一行包含一个整数t（1≤t≤100）——测试用例的数量。 每个测试用例的第一行包含两个正整数n和m（2≤n≤2×10^5；1≤m≤n）——士兵的数量和条件的数量。 然后是m行，每行包含3个整数：a_i、b_i、d_i（a_i ≠ b_i；1≤a_i，b_i≤n；-10^9≤d_i≤10^9）——表示题目中解释的条件。注意，如果d_i为正，a_i应该在b_i的d_i米前，如果为负，a_i应该在b_i的-d_i米后。 注意，所有测试用例的n之和不超过2×10^5。 **输出数据格式：** 对于每个测试用例，如果存在一个满足所有m个条件的n个士兵的排列，则输出"YES"，否则输出"NO"。