Чтобы выиграть свою самую трудную битву, Мирча придумал отличную стратегию для своей армии. У него есть \(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» в противном случае.
Обратите внимание, что два разных солдата могут быть размещены в одном лагере.
Выходные данные
Для каждого набора входных данных выведите «YES», если существует такое расположение \(n\) солдат, которое удовлетворяет всем \(m\) условиям, и «NO» в противном случае.
Примечание
В первом примере мы можем разделить солдат на лагеря следующим образом:
- Солдат \(1\) в лагере с координатой \(x = 3\).
- Солдат \(2\) в лагере с координатой \(x = 5\).
- Солдат \(3\) в лагере с координатой \(x = 9\).
- Солдат \(4\) в лагере с координатой \(x = 11\).
Для второго примера не существует разбиения, которое может удовлетворить все ограничения одновременно.
Для третьего примера не существует разбиения, которое удовлетворяет всем условиям, так как мы получаем противоречивую информацию о той же паре.
Одно из возможных разбиений, удовлетворяющих условиям в четвёртом примере:
- Солдат \(1\) в лагере с координатой \(x = 10\).
- Солдат \(2\) в лагере с координатой \(x = 13\).
- Солдат \(3\) в лагере с координатой \(x = -2023\).
- Солдат \(4\) в лагере с координатой \(x = -2023\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
YES
NO
NO
YES
|