| VK Cup 2016 - Раунд 2 |
|---|
| Закончено |
Маленький Артёмка — очень хороший программист. Он знает много разных сложных алгоритмов. В последнее время он пытается стать экспертом в решении задачи 2-SAT.
Задача 2-SAT (2-ВЫП) состоит в проверке выполнимости булевой формулы, являющейся конъюнкцией (логическим И) дизъюнкций (логическое ИЛИ), где каждая дизъюнкция содержит не больше двух литералов (переменных). В рамках данной задачи мы рассматриваем только формулы, где каждая дизъюнкия содержит ровно два литерала.
Рассмотрим пример задачи 2-SAT: 
. Обратите внимание, что в формуле могут встречаться отрицания, как например для x1 или для x4.
Артём хочет решить как можно больше задач, сводимых к 2-SAT. Он нашёл очень интересную задачку, с которой никак не может справиться, и, как обычно, просит вас помочь ему.
Задача звучит так: даны две формулы 2-SAT f и g. Определите, совпадают ли множества их решений. Если нет, то найдите любой набор переменных x, такой что f(x) ≠ g(x).
В первой строке входных данных записаны три целых числа n, m1 и m2 (1 ≤ n ≤ 1000, 1 ≤ m1, m2 ≤ n2) — количество переменных, количество дизъюнктов в первой формуле и количество дизъюнктов во второй формуле соответственно.
Следующие m1 строк содержат описание 2-SAT формулы f. Описание содержит ровно m1 пар целых чисел xi ( - n ≤ xi ≤ n, xi ≠ 0), каждая пара в отдельной строке , где xi > 0 соответствует переменной без отрицания, а xi < 0 соответствует переменной с отрицанием. Каждая пара задаёт или-пару в формуле. Пары соединяются в формуле с помощью логического И (смотрите примеры для лучшего понимания). Следующие m2 строк содержат описание 2-SAT формулы g в аналогичном формате.
Если обе формулы имеют одинаковое множество решений, выведите единственное слово «SIMILAR» (без кавычек). Иначе выведите ровно n целых чисел xi (
) — любое множество значений булевых переменных, которое удовлетворяет f(x) ≠ g(x).
2 1 1
1 2
1 2
SIMILAR
2 1 1
1 2
1 -2
0 0
В первом примере даны две одинаковые формулы, так что очевидно, что их множество решений совпадает.
Во втором примере, если мы подставим в формулу x1 = 0 и x2 = 0, мы получим 0, так как 
. Если мы подставим те же значения во вторую формулу, то её значение будет равно 1, так как 
.
