Задача
Петя и Вася с упоением играют в шпионов. Сегодня они планируют, где будут
расположены их секретные бункеры и штаб-квартира.
Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n.
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут.
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете.
Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками.
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.
Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.
Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10
5) - количество бункеров.
В следующих n - 1 строках находится по два целых числа u
i и v
i (1 <= u
i, v
i <= n, u
i ≠ v
i) - номера бункеров, которые соединяет i-ый тоннель.
Гарантируется, что между любыми двумя бункерами существует единственный путь.
Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.
Примеры:
| Входные данные |
Выходные данные |
2
1 2 |
NO |
3
1 2
2 3 |
YES |