У вас есть связный неориентированный граф, состоящий из \(n\) вершин и \(m\) ребер. У \(i\)-го узла есть начальное значение \(v_i\) и целевое значение \(t_i\).
За одну операцию можно выбрать любое ребро \((i, j)\) и добавить \(k\) к \(v_i\) и \(v_j\), где \(k\) может быть любым целым числом. В частности, \(k\) может быть отрицательным.
Ваша задача определить, можно ли, выполнив некоторое конечное число операций (возможно, ноль), добиться того, что каждого узла \(i\), \(v_i = t_i\).
Выходные данные
Для каждого наборам входных данных, если возможно, чтобы значение в каждой вершине стало равно целевому после некоторого количества операций, выведите «YES». В противном случае выведите «NO».
Примечание
Вот визуализация первого тестового случая (оранжевые значения обозначают начальные значения, а синие — целевые):
Один из возможных порядков действий для получения нужных значений для каждого узла следующий:
- Операция \(1\): Добавить \(2\) к вершинами \(2\) и \(3\).
- Операция \(2\): Добавить \(-2\) к вершинам \(1\) и \(4\).
- Операция \(3\): Добавить \(6\) к вершинам \(3\) и \(4\).
Теперь мы видим, что в общей сложности мы добавили \(-2\) к вершине \(1\), \(2\) к вершине \(2\), \(8\) к вершине \(3\) и \(4\) к вершине \(4\), что привело каждую вершину к нужному значению.
Для графа из второго набора входных данных получить нужные значения невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 4
5 1 2 -3
3 3 10 1
1 2
1 4
3 2
3 4
4 4
5 8 6 6
-3 1 15 4
1 2
1 4
3 2
3 4
|
YES
NO
|