H. Третья буква
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы выиграть свою самую трудную битву, Мирча придумал отличную стратегию для своей армии. У него есть $$$n$$$ солдат, и он решил расположить их определенным образом в лагерях. Каждый солдат должен принадлежать ровно одному лагерю, и на каждой целочисленной точке оси $$$x$$$ находится один лагерь (на точках $$$\cdots, -2, -1, 0, 1, 2, \cdots$$$).

Стратегия состоит из $$$m$$$ условий. Условие $$$i$$$ гласит, что солдат $$$a_i$$$ должен принадлежать лагерю, который находится в $$$d_i$$$ метрах перед лагерем, к которому принадлежит человек $$$b_i$$$. (Если $$$d_i < 0$$$, то лагерь $$$a_i$$$ должен быть в $$$-d_i$$$ метрах позади лагеря $$$b_i$$$.)

Теперь Мирча задается вопросом, существует ли разбиение солдат, которое удовлетворяет условию, и просит вашей помощи! Ответьте «YES», если существует разбиение из $$$n$$$ солдат, которое удовлетворяет всем $$$m$$$ условиям, и «NO» в противном случае.

Обратите внимание, что два разных солдата могут быть размещены в одном лагере.

Входные данные

Первая строка содержит одно целое число $$$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$$$ должен быть в $$$d_i$$$ метрах перед $$$b_i$$$, а если отрицательно, то $$$a_i$$$ должен быть в $$$-d_i$$$ метрах позади $$$b_i$$$.

Обратите внимание, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если существует такое расположение $$$n$$$ солдат, которое удовлетворяет всем $$$m$$$ условиям, и «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$$$.