Настав момент, якого Ви чекали усе своє життя: Ви винайшли спосіб швидко розв'язувати задачу знаходження максимальної кліки: задано неорієнтовний граф, необхідно знайти розмір максимальної підмножини його вершин, які формують кліку (усі вершини попарно з'єднано). Ця задача є NP-складною, але у Вас є доведенняо того, що P = NP!
Нажаль, наукова спільнота не бажає вас навіть слухати. Ваші документи з даного питання у даний час відхилено, тому що "не існує розв'яку очевидної нерозв'язуваної задачі". Ваш номер телефона вже у списку ігнорування в усіх професорів комп'ютерних наук, яких Ви знаєте. Світ, здається, ненавидить Вас.
Тоді Ви вирішили створити алгоритм розв'язання задачі знаходження максимальної кліки і помістити його в Інтернеті - тоді кожен зможе перевірити самостійно, що Ви маєте рацію. Ви вже реалізували тестиуючу систему і майже запустили для цього веб-сайт, але потім Ви зрозуміли, що це була не дуже вдала ідея. Якщо Ви зробите розв'язувач доступним, то тоді кожен зможе розв'язати усі NP-задачі, звевши їх до задачі знаходження максимальної кліки. Що ж робити, коли люди просто мовчки будуть використовувати Ваше відкриття, замість того, щоб принести Вам відомість і повагу?
На щастя, єдине доведення NP-складності задачі про максимальну кліку, яке Вы знаєте, полягає у приведенні її до задачі 3-SAT достатньо специфічним методом. Тому Ви вирішили перевіритиь, чи отримано вхідний граф для Вашого розв'язувача у результаті цього приведення, я якщо да, то Ви відмовитесь розв'язувати задачу. Таким чином ніхто не зможе знайти швидкий розв'язок для задач класу NP, але кожен зможе перевірити роботу Вашого розв'язувача задавши йому на вхід граф іншого вида.
3-SAT задача формулюється настпним чином. Задано формулу у вигляді , де кожен терм t^i_j є бульовою змінною чи її запереченням (більш формально, або x_k, або ¬x_k). Необхідно визначити, чи можна присвоїти змінним значення істина/неправда так, щоб формула стала істинною. Усі три терми в одній дужці повинні задавати різні змінні.
Приведення працює наступним чином. За заданою формулою створимо граф з 3n вершинами, кожній вершині відповідає змвнна з одного виразу в дужках. Двв вершини, що відповідають термам t^i_j та t^r_s, з'єднано ребром, якщо i ≠ r (терми належать різним виразам у дужках) і терми не є суперечливи (вони або однаковв, або задають різні змінні).
На наступному рисунку зображено граф, отриманий з формули (x_1∨x_2∨¬x_3)∧(¬x_1∨¬x_2∨x_4)∧(¬x_1∨¬x_2∨¬x_4):
Кліка розміром n відповідає присвоювання змінним значень істина/неправда таким чином, що у кожному виразі в дужках хоча б одна змвнна приймає істинне значення. На рисунку виділено ребра, які формують кліку розміру 3. Установка x_1 у неправду і x_2 в істину забезпечує виконання усіх виразів в дужках, незалежно від значень змвнних x_3 і x_4.
За заданиом графом потрібно визначити, чи міг він бути отриманим в результаті вище описаного приведення. Вершини можна переставляти у довільному порядку.
Перший рядок вхідного файлу містить два цілих числа v (1 ≤ v ≤ 100) та e, які позначають відповідно кількість вершин та ребер графа. У кожному з наступних e рядків міститься по два цілих числа, які позначають номери вершин, з'єднаних ребром. Кожна пара вершин зв'язана не більше. ніж один раз, жодне ребро не з'єднує вершину саму з собою.
Виведіть "YES", якщо заданий граф можно отримати у результаті описаного приведення і "NO" у протилежному випадку.