Задачі
Максимальна кліка
Максимальна кліка
Настав момент, якого Ви чекали усе своє життя: Ви винайшли спосіб швидко розв'язувати задачу знаходження максимальної кліки: задано неорієнтовний граф, необхідно знайти розмір максимальної підмножини його вершин, які формують кліку (усі вершини попарно з'єднано). Ця задача є \textbf{NP}-складною, але у Вас є доведенняо того, що \textbf{P = NP!}
Нажаль, наукова спільнота не бажає вас навіть слухати. Ваші документи з даного питання у даний час відхилено, тому що "не існує розв'яку очевидної нерозв'язуваної задачі". Ваш номер телефона вже у списку ігнорування в усіх професорів комп'ютерних наук, яких Ви знаєте. Світ, здається, ненавидить Вас.
Тоді Ви вирішили створити алгоритм розв'язання задачі знаходження максимальної кліки і помістити його в Інтернеті - тоді кожен зможе перевірити самостійно, що Ви маєте рацію. Ви вже реалізували тестиуючу систему і майже запустили для цього веб-сайт, але потім Ви зрозуміли, що це була не дуже вдала ідея. Якщо Ви зробите розв'язувач доступним, то тоді кожен зможе розв'язати усі \textbf{NP}-задачі, звевши їх до задачі знаходження максимальної кліки. Що ж робити, коли люди просто мовчки будуть використовувати Ваше відкриття, замість того, щоб принести Вам відомість і повагу?
На щастя, єдине доведення \textbf{NP}-складності задачі про максимальну кліку, яке Вы знаєте, полягає у приведенні її до задачі \textbf{3-SAT} достатньо специфічним методом. Тому Ви вирішили перевіритиь, чи отримано вхідний граф для Вашого розв'язувача у результаті цього приведення, я якщо да, то Ви відмовитесь розв'язувати задачу. Таким чином ніхто не зможе знайти швидкий розв'язок для задач класу \textbf{NP}, але кожен зможе перевірити роботу Вашого розв'язувача задавши йому на вхід граф іншого вида.
\includegraphics{https://static.e-olymp.com/content/a7/a704f051bbdb76797e5fb636ba0279c540d02f0c.jpg}
\textbf{3-SAT} задача формулюється настпним чином. Задано формулу у вигляді , де кожен терм \textbf{t^i_j} є бульовою змінною чи її запереченням (більш формально, або \textbf{x_k}, або ¬\textbf{x_k}). Необхідно визначити, чи можна присвоїти змінним значення істина/неправда так, щоб формула стала істинною. Усі три терми в одній дужці повинні задавати різні змінні.
Приведення працює наступним чином. За заданою формулою створимо граф з \textbf{3n} вершинами, кожній вершині відповідає змвнна з одного виразу в дужках. Двв вершини, що відповідають термам \textbf{t^i_j} та \textbf{t^r_s}, з'єднано ребром, якщо \textbf{i }≠ \textbf{r} (терми належать різним виразам у дужках) і терми не є суперечливи (вони або однаковв, або задають різні змінні).
На наступному рисунку зображено граф, отриманий з формули \textbf{(x_1∨x_2∨¬x_3)∧(¬x_1∨¬x_2∨x_4)∧(¬x_1∨¬x_2∨¬x_4)}:
\includegraphics{https://static.e-olymp.com/content/5f/5f0a92c8da51979e69d19e98274f395b71cac8b5.jpg}
Кліка розміром \textbf{n} відповідає присвоювання змінним значень істина/неправда таким чином, що у кожному виразі в дужках хоча б одна змвнна приймає істинне значення. На рисунку виділено ребра, які формують кліку розміру \textbf{3}. Установка \textbf{x_1} у неправду і \textbf{x_2} в істину забезпечує виконання усіх виразів в дужках, незалежно від значень змвнних \textbf{x_3} і \textbf{x_4}.
За заданиом графом потрібно визначити, чи міг він бути отриманим в результаті вище описаного приведення. Вершини можна переставляти у довільному порядку.
\InputFile
Перший рядок вхідного файлу містить два цілих числа \textbf{v} (\textbf{1} ≤ \textbf{v} ≤ \textbf{100}) та \textbf{e}, які позначають відповідно кількість вершин та ребер графа. У кожному з наступних \textbf{e} рядків міститься по два цілих числа, які позначають номери вершин, з'єднаних ребром. Кожна пара вершин зв'язана не більше. ніж один раз, жодне ребро не з'єднує вершину саму з собою.
\OutputFile
Виведіть "\textbf{YES}", якщо заданий граф можно отримати у результаті описаного приведення і "\textbf{NO}" у протилежному випадку.
Вхідні дані #1
9 22 1 3 1 6 7 1 8 9 9 1 2 3 2 4 2 5 2 6 2 8 3 4 3 5 3 7 4 8 4 9 5 6 5 7 5 8 5 9 6 7 6 9 7 8
Вихідні дані #1
YES