Codeforces Round 886 (Div. 4) |
---|
Закончено |
Чтобы выиграть свою самую трудную битву, Мирча придумал отличную стратегию для своей армии. У него есть $$$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» в противном случае.
45 31 2 22 3 44 2 -66 51 2 22 3 44 2 -65 4 43 5 1002 21 2 51 2 44 11 2 3
YES NO NO YES
В первом примере мы можем разделить солдат на лагеря следующим образом:
Для второго примера не существует разбиения, которое может удовлетворить все ограничения одновременно.
Для третьего примера не существует разбиения, которое удовлетворяет всем условиям, так как мы получаем противоречивую информацию о той же паре.
Одно из возможных разбиений, удовлетворяющих условиям в четвёртом примере:
Название |
---|