Наступил момент, которого Вы ждали всю свою жизнь: Вы изобрели способ быстро решать задачу нахождения максимальной клики: задан неориентированный граф, необходимо найти размер максимального подмножества его вершин, которые формируют клику (все вершины попарно соединены). Эта задача является NP-трудной, но у вас имеется доказательство того, что P = NP!
К сожалению, научное сообщество не хочет вас даже слушать. Ваши документы по данному вопросу в настоящее время отвергнуты, потому что "нет решения очевидной неразрешимой задачи". Ваш номер телефона уже в списке игнорирования у всех профессоров компьютерных наук, которых вы знаете. Мир, кажется, ненавидит вас.
Тогда вы решили создать алгоритм решения задачи нахождения максимальной клики и поместить его в Интернете - тогда каждый сможет проверить самостоятельно, что вы правы. Вы уже реализовали тестирующую систему и почти запустили для этого веб-сайт, но потом Вы поняли, что это была не очень хорошая идея. Если Вы сделаете решатель доступным, то тогда каждый сможет решить все NP-задачи, сведя их к задаче нахождения максимальной клики. Что же делать, если люди просто молча будут использовать Ваше открытие, вместо того, чтобы принести Вам известность и уважение?
К счастью, единственное доказательство NP-трудности задачи о максимальной клике, которое Вы знаете, состоит в сведении ее к задаче 3-SAT достаточно специфическим методом. Поэтому Вы решили проверить, получен ли входной граф для Вашего решателя в результате этого сведения, и если да, то Вы откажитесь решать задачу. Таким образом никто не сможет найти быстрое решение для задач класса NP, но каждый сможет проверить работу Вашего решателя задав ему на вход граф другого вида.
3-SAT задача формулируется следующим образом. Задана формула в виде , где каждый терм t^i_j является булевой переменной или ее отрицанием (более формально, или x_k, или ¬x_k). Необходимо определить, можно ли присвоить переменным значения истина/ложь так чтобы формула стала истинной. Все три терма в одной скобке должны представлять разные переменые.
Сводимость работает следующим образом. По исходной формуле создадим граф с 3n вершинами, каждый вершине соответствует переменная из одного скoбочного выражения. Две вершины, соответствующие термам 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" в противном случае.