Дядя Богдан, будучи матросом на корабле капитана Флинта, порой скучает по родине. Сегодня он рассказал о том, как в его государстве вводили индекс счастья населения.
Всего в стране \(n\) городов и \(n−1\) двусторонняя дорога, соединяющая некоторые пары городов. Из любого города можно попасть в любой другой, пройдя по некоторым дорогам. Города пронумерованы от \(1\) до \(n\) и город \(1\) является столицей. Таким образом, структура государства является корневым деревом.
Всего в стране проживает \(m\) человек. В \(i\)-м городе проживает \(p_i\) человек, но все работают в столице. После напряженного рабочего дня, каждый из жителей возвращается в свой город по кратчайшему пути.
У каждого жителя есть свое настроение: кто-то уходит с рабочего места в хорошем настроении, а у кого-то настроение уже испорчено. Более того, и по пути домой настроение жителя может испортиться. Если настроение человека испортилось, то оно уже не может улучшиться.
В каждом городе установлен детектор настроения — он отслеживает настроение каждого, кто побывал в этом городе. Детектор настроения \(i\)-го города считает индекс счастья \(h_i\) как количество человек в хорошем настроении минус количество в плохом. Для простоты будем считать, что настроение жителя внутри города не меняется.
Детектор настроения — это новая разработка и нет полной уверенности, что все приборы отработают должным образом. После того, как все жители страны добрались до своих городов, власти обратились к Дяде Богдану, лучшему программисту государства, с просьбой определить корректны ли данные индекса счастья всех городов или где-то закралась ошибка.
Дядя Богдан успешно справился с задачей. А удастся ли это Вам?
Более формально, Вам требуется определить: «Возможно ли, что, после возвращения всех жителей по домам, для каждого города \(i\) будет верно, что индекс счастья в этом городе в точности равен \(h_i\)».
Выходные данные
Для каждого набора входных данных выведите YES, если все детекторы настроения исправны или NO — иначе. Буквы в словах YES и NO можно выводить в любом регистре.
Примечание
Рассмотрим первый набор входных данных первого теста:
Под конец рабочего дня все жители страны находятся в столице. Рассмотрим один из возможных вариантов развития событий:
- житель города \(1\): живет в столице и его настроение не ухудшалось;
- житель города \(4\): посетил города \(1\) и \(4\), настроение ухудшилось между городами \(1\) и \(4\);
- житель города \(3\): посетил города \(1\) и \(3\) в хорошем настроении;
- житель города \(6\): посетил города \(1\), \(3\) и \(6\), настроение ухудшилось между городами \(1\) и \(3\);
Таким образом,
- \(h_1 = 4 - 0 = 4\),
- \(h_2 = 0\),
- \(h_3 = 1 - 1 = 0\),
- \(h_4 = 0 - 1 = -1\),
- \(h_5 = 0\),
- \(h_6 = 0 - 1 = -1\),
- \(h_7 = 0\).
Второй набор первого теста:
У всех жителей страны уже испортилось настроение в столице. Это единственный возможный вариант развития событий.
Первый набор второго теста:
Второй набор второго теста:
Можно показать, что требуемые значения индексов счастья недостижимы в обоих наборах второго теста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
7 4
1 0 1 1 0 1 0
4 0 0 -1 0 -1 0
1 2
1 3
1 4
3 5
3 6
3 7
5 11
1 2 5 2 1
-11 -2 -6 -2 -1
1 2
1 3
1 4
3 5
|
YES
YES
|
|
2
|
2
4 4
1 1 1 1
4 1 -3 -1
1 2
1 3
1 4
3 13
3 3 7
13 1 4
1 2
1 3
|
NO
NO
|