Обратите внимание, что это первая задача из двух похожих задач. Вы можете взламывать эту задачу только тогда, когда решите обе задачи.
Вам дано дерево с \(n\) вершинами. Изначально на каждом ребре написан \(0\). За одну операцию вы можете выбрать любые \(2\) различных листа \(u\), \(v\) и любое действительное число \(x\), и прибавить \(x\) ко всем числам записанных на ребрах на простом пути с \(u\) до \(v\).
Для примера на изображении ниже показан результат применения двух операций к графу: прибавления \(2\) на пути от \(7\) до \(6\), а потом прибавления \(-0.5\) на пути от \(4\) до \(5\).
Верно ли, что для любой конфигурации действительных чисел записанных на ребрах, мы можем достичь ее, выполнив конечное число операций?
Лист — это вершина степени \(1\). Простой путь — это путь, не содержащий ни одну вершину дважды.
Выходные данные
Если существует конфигурация действительных чисел записанных на ребрах дерева, которой мы не можем достичь выполнением операций, выведите «NO».
Иначе выведите «YES».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
Примечание
В первом примере, мы можем прибавить любое действительное \(x\) к числу записанному на единственному ребре \((1, 2)\).
Во втором примере одной из конфигураций, которые мы не можем достичь, является \(0\) записанный на \((1, 2)\) и \(1\) записанная на \((2, 3)\).
Ниже изображены графы с примеров \(3\), \(4\):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
YES
|
|
2
|
3
1 2
2 3
|
NO
|
|
3
|
5
1 2
1 3
1 4
2 5
|
NO
|
|
4
|
6
1 2
1 3
1 4
2 5
2 6
|
YES
|