Бункери#2784
Петя і Вася із захопленням грають у шпигунів. Сьогодні вони планують, де розмістити свої секретні бункери та штаб-квартиру.
Вони вирішили, що їм потрібно рівно бункерів, які для секретності будуть пронумеровані від до . Деякі з цих бункерів будуть з’єднані двонаправленими тунелями так, щоб, для надійності й секретності, між будь-якими двома бункерами існував єдиний шлях. Петя і Вася вже визначили, які бункери будуть поєднані тунелями, але не можуть вирішити, який обрати штаб-квартирою.
Вони хочуть вибрати штаб-квартиру та поділити решту бункерів між собою так, щоб кожен отримав однакову кількість бункерів і було рівно два тунелі, які ведуть до штаб-квартири: один з бункера, що належить Васі, і один з бункера, що належить Петі.
Після довгого дня Петя пішов додому, а вранці Вася показав йому план, на якому бункери були позначені точками, а тунелі — лініями. Вася вибрав штаб-квартиру так, щоб план був симетричним відносно прямої, що проходить через точку, яка відповідає штаб-квартирі.
Хоча Петя одразу зауважив, що Вася припустився помилки й не намалював половину бункерів, йому стало цікаво, чи взагалі можливо обрати штаб-квартиру й намалювати такий симетричний план.
Перший рядок вхідних даних містить одне ціле число (1 \leq n \leq 10^5) — кількість бункерів. У наступних n-1 рядках міститься по два цілих числа u_i та v_i (1 \leq u_i, v_i \leq n, u_i \ne v_i) — номери бункерів, з’єднаних -м тунелем. Гарантується, що між будь-якими двома бункерами існує єдиний шлях.
Виведіть YES, якщо можливо обрати штаб-квартиру й намалювати такий симетричний план, або NO, якщо це неможливо.
Приклад 1