Задачи
Максимальная клика
Максимальная клика
Наступил момент, которого Вы ждали всю свою жизнь: Вы изобрели способ быстро решать задачу нахождения максимальной клики: задан неориентированный граф, необходимо найти размер максимального подмножества его вершин, которые формируют клику (все вершины попарно соединены). Эта задача является \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} вершинами, каждый вершине соответствует переменная из одного скoбочного выражения. Две вершины, соответствующие термам \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