Максимальна кліка#3411
Настав момент, на який ви чекали все життя: ви винайшли спосіб швидко розв'язувати задачу знаходження максимальної кліки: задано неорієнтований граф, необхідно знайти розмір максимальної підмножини його вершин, які утворюють кліку (усі вершини попарно з'єднані). Ця задача є NP-складною, але ви маєте доведення, що P = NP!
На жаль, наукова спільнота не бажає вас навіть слухати. Ваші роботи з цієї теми відхиляють, бо це "розв'язок очевидно нерозв'язуваної задачі". Ваш номер телефона вже у списку ігнорування всіх відомих вам професорів інформатики. Здається, світ вас ненавидить.
Тому ви вирішили створити solver для задачі максимальної кліки й викласти його онлайн, щоб кожен міг переконатися, що ви праві. Ви вже реалізували програму й майже запустили сайт, але потім зрозуміли, що це не дуже гарна ідея: якщо зробити solver відкритим, кожен зможе вирішити будь-яку задачу з NP, зводячи її до задачі про максимальну кліку. А раптом люди просто мовчки цим скористаються і не принесуть вам ані слави, ані поваги?
На щастя, єдине відоме вам доведення NP-складності задачі про максимальну кліку працює через зведення задачі 3-SAT певним чином. Тож ви вирішили перевіряти, чи введений граф міг бути отриманий цим зведенням, і, якщо так, відмовити у вирішенні задачі. Так ніхто не зможе отримати швидкі розв'язки всіх задач з NP, але всі зможуть перевірити ваш алгоритм на інших графах.
Задача 3-SAT формулюється так: задано формулу типу , де кожен терм t^i_j — булева змінна або її заперечення (тобто x_k або \neg x_k). Необхідно з'ясувати, чи існує призначення істина/хибно для змінних, таке, щоб формула була істинна. Усі три терми в одній дужці повинні відповідати різним змінним.
Зведення працює так. З формули будуємо граф з вершин — по одній на кожний терм кожної дужки. Дві вершини t^i_j і t^r_s сполучають ребром, якщо i \ne r (терми належать різним дужкам) і вони не суперечать одна одній (тобто однакові або містять різні змінні).
Рисунок нижче ілюструє граф, отриманий за формулою (x_1 x_2 x_3) (x_1 x_2 x_4) (x_1 x_2 x_4):
Кліка розміру відповідає присвоєнню змінним значень істина/хибність так, щоб у кожній дужці хоча б один терм був істинний. Виділені ребра формують кліку розміру — встановлення x_1 = \text{хибно} та x_2 = \text{істинно} задовольняє усі дужки незалежно від значень x_3 і x_4.
Визначте, чи міг заданий граф бути отриманий цим зведенням. Вершини розміщені у довільному порядку.
Перший рядок містить два числа (1 \leq v \leq 100) і — кількість вершин та ребер у графі. Далі у рядках по два числа — номери вершин, з'єднаних ребром. Пара вершин сполучена не більш як одним ребром, жодна петля не допускається.
Виведіть "YES", якщо заданий граф міг бути отриманий описаним способом, або "NO" інакше.
Приклад 1