Настав грудень, і разом з ним настав час готуватися до святкування Різдва. На острові лицарів та брехунів це свято традиційно відзначається дуже масштабно. Святковий стіл, роздвʼяна ялинка, конфетті та бенгальські вогні — все готове до початку урочистостей.

Як ви знаєте, на острові лицарів і брехунів живуть лише два види мешканців — лицарі та брехуни. Лицарі ніколи не брешуть, оскільки цього їм не дозволяють їхні високі моральні принципи. Брехуни ж, навпаки, завжди говорять лише неправду.

Найважливішою частиною святкування Різдва є хоровод навколо ялинки. Усі запрошені мешканці острова беруться за руки та рухаються по колу під музику. Оскільки населення острова дуже консервативне, то цього року жителі хочуть вишикуватися в коло в тому ж порядку, що й минулого. Однак даних про те, як було влаштовано хоровод, не збереглося. Відомо лише, що кожен житель острова запам'ятав, ким були його сусіди з хороводу (лицарями чи брехунами).

Опитавши кожну людину, запрошену на святкування, ви дізналися, ким були їхні сусіди за їхніми словами (при цьому брехуни говорять неправду про кожного сусіда). Залишилося тільки придумати якесь розташування мешканців острова в коло так, щоб їх свідчення не суперечили одне одному.

Напишіть програму, яка за списком жителів та їх свідчень визначить, чи існує таке розташування чи вишикуватися в хоровод як минулого року не вийде.

Формат вхідних даних

У першому рядку вхідних даних дано ціле число \(n\) (\(2 ≤ n ≤ 10^5\)) - кількість жителів на острові брехунів.

У наступних \(n\) рядках дано цілі числа \(l_i\) і \(r_i\) (\(0 ≤ l_i, r_i ≤ 1\)) - дані про сусідів \(i\)-ї людини. Якщо \(l_i\) = 0, то \(i\)-й житель стверджує, що його сусід по хороводу у напрямку проти годинникової стрілки був брехуном, а якщо \(l_i\) = 1, то лицарем. Аналогічно, число \(r_i\) містить інформацію про сусіда за годинниковою стрілкою.

Формат вихідних даних

Потрібно вивести «Yes», якщо існує спосіб вишикувати людей за вказаними правилами, або «No», якщо не вдається.

Оцінювання

Тести до цього завдання складаються із чотирьох груп.

• Тести 1 - 2. Тести з умови оцінюються в нуль балів.
• Тести 3-10. На тести цієї групи накладається обмеження \(n ≤ 10\). Група тестів оцінюється в 20 балів, бали ставляться тільки при проходженні всіх тестів групи.
• Тести 11 - 26. На тести цієї групи накладається обмеження \(n ≤ 20\). Група тестів оцінюється в 25 балів, бали ставляться тільки при проходженні всіх тестів групи.
• Тести 27 - 38. У тестах цієї групи додаткових обмежень відсутні. Група оцінюється в 55 балів, бали ставляться лише за проходження всіх тестів групи.

Примітка

У першому прикладі можна побудувати мешканців у порядку (2, 1, 3, 5, 4) за годинниковою стрілкою. Показання всіх людей сходитимуться в цьому випадку, наприклад, коли четвертий житель буде лицарем, а решта чотирьох людей — брехунами.

У другому прикладі, очевидно, не можна отримати жодного рішення, оскільки вибудувати двох людей у хоровод можна лише одним способом. Розглянемо два випадки: якщо перша людина - лицар, то, за його словами, друга людина - брехун, однак, з брехливості його слів випливає, що перша людина не лицар. З іншого боку, якщо перша людина - брехун, то з її показань випливає, що друга людина - лицар, але друга людина каже, що перша - теж лицар. Таким чином, оскільки в обох випадках ми одержали протиріччя, не існує способу побудувати хоровод із наявного набору мешканців.

Приклад вхідних даних

5
1 1
0 1
1 1
0 0
1 0

Приклад вихідних даних

Yes

Приклад вхідних даних

2
0 0
1 1

Приклад вихідних даних

No